मान लीजिए कि हमारे पास समान लंबाई के दो स्ट्रिंग्स P और Q हैं, जिनमें केवल लोअर केस लेटर्स हैं, हमें स्ट्रिंग P पर प्री-प्रोसेसिंग मूव्स की न्यूनतम संख्या को गिनना होगा, इसे नीचे के ऑपरेशनों को लागू करने के बाद स्ट्रिंग Q के बराबर बनाने के लिए आवश्यक है -
-
कोई भी अनुक्रमणिका i चुनें और वर्ण pi और qi स्वैप करें।
-
कोई भी अनुक्रमणिका i चुनें और वर्ण pi और pn – i – 1 स्वैप करें।
-
कोई भी अनुक्रमणिका i चुनें और वर्ण qi और qn – i – 1. स्वैप करें।
नोट - रेंज में i का मान (0 i
एक चाल में हम अंग्रेजी वर्णमाला के किसी अन्य वर्ण के साथ P के किसी वर्ण को बदल सकते हैं।
इसलिए, यदि इनपुट P ="pqprpqp", Q ="qprpqpp" जैसा है, तो आउटपुट 4 होगा जैसे कि हम P0 ='q', P2 ='r', P3 ='p' और P4 ='सेट करते हैं। q' और P "qqrpqqp" होगा। उसके बाद हम संचालन के निम्नलिखित अनुक्रम द्वारा समान तार प्राप्त कर सकते हैं:स्वैप (P1, Q1) और स्वैप (P1, P5)।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=P का आकार
-
रेस :=0
-
मैं के लिए 0 से n / 2 की सीमा में, करते हैं
-
my_map :=एक नया नक्शा
-
my_map[P[i]] :=1
-
यदि P[i], P[n - i - 1] के समान है, तो
-
my_map[P[n - i - 1]] :=my_map[P[n - i - 1]] + 1
-
-
अगर Q[i] my_map में है, तो
-
my_map[Q[i]] :=my_map[Q[i]] + 1
-
-
अन्यथा,
-
my_map[Q[i]] :=1
-
-
अगर Q[n - i - 1] my_map में है, तो
-
my_map[Q[n - 1 - i]] :=my_map[Q[n - 1 - i]] + 1
-
-
अन्यथा,
-
my_map[Q[n - 1 - i]] :=1
-
-
आकार :=my_map का आकार
-
अगर आकार 4 के समान है, तो
-
रेस :=रेस + 2
-
-
अन्यथा जब आकार 3 के समान हो, तब
-
res :=res + 1 + (1 जब (P[i] P[n - i - 1] के समान हो), अन्यथा 0)
-
-
अन्यथा जब आकार 2 के समान हो, तब
-
res :=res + my_map[P[i]] 2 के समान नहीं है
-
-
-
यदि n mod 2 1 के समान है और P[n / 2] Q[n / 2] के समान नहीं है, तो
-
रेस :=रेस + 1
-
-
रिटर्न रेस
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def count_preprocess(P, Q): n = len(P) res = 0 for i in range(n // 2): my_map = dict() my_map[P[i]] = 1 if P[i] == P[n - i - 1]: my_map[P[n - i - 1]] += 1 if Q[i] in my_map: my_map[Q[i]] += 1 else: my_map[Q[i]] = 1 if Q[n - i - 1] in my_map: my_map[Q[n - 1 - i]] += 1 else: my_map[Q[n - 1 - i]] = 1 size = len(my_map) if (size == 4): res += 2 elif (size == 3): res += 1 + (P[i] == P[n - i - 1]) elif (size == 2): res += my_map[P[i]] != 2 if (n % 2 == 1 and P[n // 2] != Q[n // 2]): res += 1 return res A = "pqprpqp" B = "qprpqpp" print(count_preprocess(A, B))
इनपुट
"pqprpqp", "qprpqpp"
आउटपुट
4