資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中特殊等價字串的組
假設我們有一個名為 A 的字串陣列。對 S 的一次移動包括交換 S 的任意兩個偶數索引字元，或任意兩個奇數索引字元。
現在，如果在對 S 進行任意次數的移動後，S 與 T 相同，則兩個字串 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","z zyx"]))
輸入
["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
輸出
3
更新於: 2020年7月4日
239 次瀏覽
廣告