如何查找給定輸入中的所有循環移位字符串？

這是一個編碼練習。假設我必須決定是否一個字符串是由另一個循環移位創建的。例如：cab是循環移位abc，但是cba不是。如何查找給定輸入中的所有循環移位字符串？

給定兩個字符串s1和s2我們能做到這一點，如下所示：

 
if (s1.length != s2.length) 
    return false 
for(int i = 0; i < s1.length(); i++) 
    if ((s1.substring(i) + s1.substring(0, i)).equals(s2)) 
    return true 
return false

現在，如果我有一個字符串數組，並希望找到屬於彼此的循環移位所有字符串？例如：["abc", "xyz", "yzx", "cab", "xxx"] -> ["abc", "cab"], ["xyz", "yzx"], ["xxx"]

它看起來像我必須檢查所有對的字符串。有沒有「更好」（更高效）的方法來做到這一點？

來源

2012-01-15 Michael

關於如何在表格中查找對，可能有很多更好的方法，但我首先想到的是對錶格進行排序並應用每個相鄰對的檢查。

這是通過旋轉的所有字符串到一些更好的和更簡單，檢查每串表中的所有其他字符串

來源

2012-01-15 15:20:39 Cratylus

相比，如果在列表中字符串的數量串很短，你可以做顯著更好正常形式（例如，字典最小值）。然後按照字典順序排序並查找相同字符串的運行。那是O（n log n），我想......忽略字符串長度。可能會嘗試一些東西。

來源

2012-01-15 15:54:52 Patrick87

考慮爲每個想要測試的字符串構建一個自動機。

每個自動機應該對字符串中的每個可能字符都有一個入口點，併爲每個字符進行轉換，再加上從結尾到開始的額外轉換。

如果您合併自動機，您甚至可以進一步提高性能。

來源

2012-01-15 16:09:38 Marcin

作爲開始，你可以知道，如果一個字符串s1是字符串s2的旋轉一起包含單個（）調用，就像這樣：

public boolean isRotation(String s1, String s2){ 
    String s2twice = s2+s2; 
    return s2twice.contains(s1); 
}

也就是說，如果S1是「旋轉」和s2是「otationr」，concat給你一個「otationrotation」，它確實包含了s1。現在，即使我們假設這是線性的，或者接近它（例如使用拉賓卡爾普不是不可能的），你仍然留下O（n^2）對比較，這可能也是如此許多。

你可以做的是建立一個散列表，其中排序後的單詞是關鍵字，並且發佈列表包含列表中的所有單詞，如果排序，則給出該單詞（即.key（「bca」）和key （「CAB」）都應該返回「ABC」）：

private Map<String, List<String>> index; 
    /* ... */ 
public void buildIndex(String[] words){ 
    for(String word : words){ 
     String sortedWord = sortWord(word); 
     if(!index.containsKey(sortedWord)){ 
      index.put(sortedWord, new ArrayList<String>()); 
     } 
     index.get(sortedWord).add(word); 
    } 
}

警告：哈希表將包含針對每一個琴鍵，所有具有確切發生的次數相同量的相同字母的話（不只是輪換，即「abba」和「baba」將具有相同的鍵，但是是旋轉（「abba」，「baba」）將返回錯誤）。

但是，一旦你建立了這個索引，你可以大大減少你需要考慮的對的數量：如果你想要所有的「bca」旋轉，你只需要排序（「bca」），查找它散列表和檢查（如果需要，使用上面的isRotation方法），如果發佈列表中的單詞是否是循環的結果。

來源

2012-01-15 16:38:55

他的問題是'language-agnostic'。 – Cratylus 2012-01-15 18:28:02

爲了舉例，我在Java中提供了片段...我使用了散列表和字符串，我會說解決方案也是語言不可知的，不是嗎？ – 2012-01-15 18:46:31

我認爲由Patrick87和savinos的答案組合會產生相當大的意義。具體而言，在Java式的僞代碼：

List<String> inputs = ["abc", "xyz", "yzx", "cab", "xxx"]; 
Map<String,List<String>> uniques = new Map<String,List<String>>(); 
for(String value : inputs) { 
    String normalized = normalize(value); 
    if(!uniques.contains(normalized)) { 
     unqiues.put(normalized, new List<String>()); 
    } 
    uniques.get(normalized).add(value); 
} 
// you now have a Map of normalized strings to every string in the input 
// that is "equal to" that normalized version

規格化的字符串，如Patrick87說可能是最好的選擇導致最低的詞素文字順序串的旋轉來完成。

值得一但指出的是，「最好」的算法可能在很大程度上依賴於輸入...串的數量，這些字符串的長度，有多少重複的有等

來源

2012-01-16 14:33:31 RHSeeger

您可以在O（s）時間內使用Booth算法（https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation）將所有字符串旋轉爲標準化形式，其中s是字符串的長度。

然後，您可以使用規範化形式作爲HashMap中的鍵（其中值是在輸入中看到的一組旋轉）。您可以通過數據一次性填充此HashMap。即，每串

計算標準化形式
檢查，如果HashMap中包含的標準化形式的關鍵 - 如果不插入空集在這個關鍵
字符串添加到集合中HashMap

然後您只需要輸出HashMap的值。這使得算法O（n * s）的總運行時間 - 其中n是單詞數量，s是平均單詞長度。總空間使用量也是O（n * s）。

來源

2016-11-13 21:01:10

如何查找給定輸入中的所有循環移位字符串？

回答

相關問題