पायथन में विशेष-समतुल्य स्ट्रिंग्स के समूह

मान लीजिए हमारे पास A नामक स्ट्रिंग्स की एक सरणी है। S पर एक चाल में S के किन्हीं दो सम इंडेक्स वाले वर्णों को स्वैप करना, या किन्हीं दो विषम इंडेक्स वाले वर्णों को स्वैप करना शामिल है।

अब, दो स्ट्रिंग्स S और T विशेष-समतुल्य हैं यदि S पर किसी भी संख्या में चालें करने के बाद, S, T के समान है। तो, यदि S = "zzxy" और T = "xyzz" विशेष-समतुल्य हैं क्योंकि हम "zzxy" से "xzzy" से "xyzz" जैसी चालें बना सकते हैं जो S[0] और S[2] को स्वैप करती हैं, फिर S[1] और S[3] को।

अब, A से विशेष-समतुल्य स्ट्रिंग्स का एक समूह A का एक गैर-खाली उपसमुच्चय है जैसे कि -

समूह में स्ट्रिंग्स के प्रत्येक जोड़े विशेष-समतुल्य हैं, और समूह का आकार अधिकतम संभव है (ऐसी कोई स्ट्रिंग S नहीं है जो समूह में नहीं है जैसे कि S उस समूह में हर स्ट्रिंग के लिए विशेष-समतुल्य है) हमें A से विशेष-समतुल्य स्ट्रिंग्स के समूहों की संख्या ढूंढनी है।

तो, यदि इनपुट ["abcd","cdab","cbad","xyzz","zzxy","zzyx"] जैसा है, तो आउटपुट 3 होगा, क्योंकि एक समूह ["abcd", "cdab", "cbad"] है, चूंकि वे सभी जोड़े में विशेष-समतुल्य हैं, और अन्य कोई स्ट्रिंग इन सभी के लिए जोड़े में विशेष-समतुल्य नहीं है। दो अन्य समूह भी हैं। ये ["xyzz", "zzxy"] और ["zzyx"] हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• codes := एक नया सेट
• A में प्रत्येक शब्द के लिए, करें
  • code := सम इंडेक्स वाले वर्णों की सॉर्ट की गई स्ट्रिंग और विषम इंडेक्स वाले वर्णों की सॉर्ट की गई स्ट्रिंग को जोड़ें
  • code को codes में जोड़ें
• codes का आकार लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

class Solution:
    def numSpecialEquivGroups(self, A):
        codes = set()
        for word in A:
            code = ''.join(sorted(word[::2])) + ''.join(sorted(word[1::2]))
            codes.add(code)
        return len(codes)

ob = Solution()
print(ob.numSpecialEquivGroups(["abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"]))

इनपुट

["abcd","cdab","cbad","xyzz","zzxy","zzyx"]

आउटपुट

3