0

基本上我试图找出问题的解决方案给定一个单词和一个文本，我们需要返回 anagrams 的出现。但是，我无法完全理解那里发布的一些解决方案。因此，我试图将问题转换为查找给定文本排列的问题。这是我的算法（伪代码），我想了解一下它是否正确，也想了解一下它的复杂性。

int findAnagramOccurencesinText(String input,String find)

//generate a list of all possible permutations of the letters in find and store in a list
// eg/ if find ="dog"  then list =["god","odg","dog","gdo","ogd","dgo"]

int occurances=0;
for String (perm:list)
{
     index=-1;
     while(index<input.length)
      {
          index=input.indexOf(perm,index);
          if(index!=-1)
             occurances++;
          index+=1;

      }
}
return occurances;
}

复杂度也是 O(#inputlength) 吗？任何关于如何找到这个特定算法的复杂性（如果它是正确的）的见解将不胜感激。

编辑：我知道这是一个 O(n!) 解决方案。我可以对其进行任何修改以提高效率吗？（除了废弃整个方法并转向链接问题中提到的 O(n) 方法）

4

1 回答 1

0

有一组元素的O(n!)排列。n

因此，假设字符串搜索算法是线性时间，时间复杂度为：

O((findLength)! inputLength)

以上假设findis 没有重复，如果不是，则公式稍微复杂一些。

于 2013-11-04T06:18:07.823 回答