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

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

如果字符串与列表中的字符串数相比较短,则可以通过将所有字符串旋转到某个正常形式(例如,字典最小值)来做得更好.然后按字典顺序排序并查找相同字符串的运行.那是O(n log n),我认为......忽略了弦长.也许可以试试.

Answer 2

首先,您可以通过对contains()的单次调用来了解字符串s1是否是字符串s2的旋转,如下所示:

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

也就是说,如果s1是"旋转"而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);
    }
}

CAVEAT:对于每个键,散列表将包含具有完全相同字母的所有单词出现相同的次数(不仅仅是旋转,即"abba"和"baba"将具有相同的键但是isRotation(" abba","baba")将返回false).

但是一旦你构建了这个索引,就可以大大减少你需要考虑的对数:如果你想要"bca"的所有轮换,你只需要排序("bca"),在哈希表中查找,如果发布列表中的单词是轮换的结果,则检查(使用上面的isRotation方法,如果需要).