मान लीजिए कि हमारे पास एक स्ट्रिंग s है, हमें s के सबस्ट्रिंग्स पर क्वेरी करनी है। प्रत्येक क्वेरी क्वेरी [i] के लिए, तीन भाग होते हैं [बाएं, दाएं, के], हम सबस्ट्रिंग एस [बाएं], ..., एस [दाएं] को पुनर्व्यवस्थित कर सकते हैं, और फिर उनमें से k को बदलने के लिए चुन सकते हैं कोई भी लोअरकेस अंग्रेजी अक्षर। यदि उपरोक्त वर्णित संचालन के बाद सबस्ट्रिंग एक पैलिंड्रोम होना संभव है, तो क्वेरी का परिणाम सत्य है। अन्यथा झूठा। हमें एक सरणी उत्तर [] खोजना है, जहां उत्तर [i] i-th क्वेरी क्वेरी [i] का परिणाम है।
उदाहरण के लिए, यदि इनपुट "abcda" है, तो क्वेरी [[3,3,0], [1,2,0], [0,3,1], [0,3,2], [0, 4,1]], तो आउटपुट [सत्य, झूठा, झूठा, सत्य, सत्य] होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- हल नामक एक विधि को परिभाषित करें, यह डीपी मैट्रिक्स, और q लेगा। यह नीचे की तरह काम करेगा -
- l :=q[0], r :=q[1], k :=q[2], फिर l और r को 1 से बढ़ाएं:=0
- मैं के लिए 0 से 25 की सीमा में
- एक :=एक + (dp[r, i] – dp[l – 1, i]) mod 2
- सही लौटें, जब एक / 2 का पूर्णांक विभाजन <=k, अन्यथा गलत
- मेकडीपी () नामक एक अन्य विधि को परिभाषित करें, यह डीपी मैट्रिक्स और एस लेगा, यह नीचे की तरह काम करेगा -
- मैं के लिए 0 से लंबाई की सीमा में
- जे के लिए 0 से 25 की सीमा में
- dp[i, j] :=dp[i – 1, j]
- dp[i, s का ASCII [i] - 'a' का ASCII] 1 तक बढ़ाएं
- जे के लिए 0 से 25 की सीमा में
- मुख्य विधि इस प्रकार होगी -
- n :=स्ट्रिंग का आकार s, s :=“ ” संयोजित s
- dp :=क्रम का एक मैट्रिक्स (n + 1) x 26, और इसे 0 से भरें
- मेकडीपी (डीपी, एस) पर कॉल करें
- res :=q की लंबाई के समान आकार की एक सरणी, और इसे असत्य से भरें
- i के लिए 0 से q - 1 की लंबाई के बीच
- res[i] :=solve(dp, q[i])
- रिटर्न रेस
उदाहरण (पायथन)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
class Solution(object):
def solve(self,dp,q):
l = q[0]
r = q[1]
k = q[2]
r+=1
l+=1
#arr = [ 0 for i in range(26)]
one = 0
for i in range(26):
one += (dp[r][i]-dp[l-1][i])%2
return one//2<=k
def make_dp(self,dp,s):
for i in range(1,len(s)):
for j in range(26):
dp[i][j] = dp[i-1][j]
dp[i][ord(s[i])-ord('a')]+=1
def canMakePaliQueries(self, s, q):
n = len(s)
s = " "+s
dp = [[0 for i in range(26)] for j in range(n+1)]
self.make_dp(dp,s)
res = [False for i in range(len(q))]
for i in range(len(q)):
res[i] = self.solve(dp,q[i])
return res
ob = Solution()
print(ob.canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]])) इनपुट
"abcda" [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
आउटपुट
[True, False, False, True, True]