string - 如何找到给定输入中的所有循环移位字符串？

Question

这是一个编码练习。假设我必须确定一个字符串是否是由另一个字符串的循环移位创建的。例如: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"]

看来我必须检查字符串的所有对。有没有“更好”(更有效)的方法来做到这一点？

Answer 1

首先，您可以通过一次调用 contains() 来知道字符串 s1 是否是字符串 s2 的旋转，如下所示:

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

也就是说，如果 s1 是“rotation”而 s2 是“otationr”，则 concat 会给你“otationrotationr”，它确实包含 s1。

现在，即使我们假设这是线性的或接近线性的(例如，使用 Rabin-Karp 并非不可能)，您仍然需要进行 O(n^2) 对比较，这可能太多了.

你可以做的是建立一个哈希表，其中排序的词是键，发布列表包含列表中的所有词，如果排序，给出键(即。键(“bca”)和键( "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”将具有相同的键但isRotation("abba", "baba") 将返回 false)。

但是一旦你建立了这个索引，你就可以显着减少你需要考虑的对的数量:如果你想要“bca”的所有旋转，你只需要排序(“bca”)，在哈希表，并检查(如果需要，使用上面的 isRotation 方法)发布列表中的单词是否是旋转的结果。