该算法查找 Anagrams 的时间复杂度和 space 复杂度是多少？

Question

我正在处理来自 Amazon Software
的面试问题问题是
"Design an algorithm to take a list of strings as well as a single input string, and return the indices of the list which are anagrams of the input string, disregarding special characters."
我能够很好地设计算法，我在伪代码中所做的是
1.Create单个输入字符串的数组字符数
2.For每个字符串列表，构造一个数组字符数
3.Compare 列表中每个字符串的字符数到单个输出字符串
4.If 同样，将其添加到包含所有字谜索引的列表中。
5.Return 该索引列表。

这是我在 Java 中的实现（有效，经过测试）

public static List<Integer> indicesOfAnag(List<String> li, String comp){
    List<Integer> allAnas = new ArrayList<Integer>();
    int[] charCounts = generateCharCounts(comp);
    int listLength = li.size();
    for(int c=0;c<listLength; c++ ){ 
        int[] charCountComp = generateCharCounts(li.get(c));
        if(isEqualCounts(charCounts, charCountComp))
            allAnas.add(c);
    }
    return allAnas;
}
private static boolean isEqualCounts(int[] counts1, int[] counts2){
    for(int c=0;c<counts1.length;c++) {
        if(counts1[c]!=counts2[c]) 
            return false;
    }
    return true;
}
private static int[] generateCharCounts(String comp) {
    int[] charCounts = new int[26];
    int length = comp.length();
    for(int c=0;c<length;c++) {
        charCounts[Character.toLowerCase(comp.charAt(c)) - 'a'] ++;
    }
    return charCounts;
}

由于列表和每个字符串的大小，我在分析该算法的 space 和时间复杂度时遇到了麻烦。
时间复杂度算法是否只是是 O(N) 其中 N 是列表的大小（处理每个字符串一次）或者我是否必须考虑每个字符串长度的复合复杂性，在这种情况下，O(N * n) 其中 n 是字符串的长度？我做了 N * n，因为你处理了 n N 次。 space 复杂度会是 O(N) 因为我正在创建 26 长度数组的 N 个副本吗？

Answer 1

And would space complexity be O(N) because I am creating N copies of the 26 length array?

是的。

Would the time complexity algorithm just be O(N) where N is the size of the list

没有。时间取决于输入字符串的大小，它将是 O(comp.length+sum_of_li_lengths)。

该算法查找 Anagrams 的时间复杂度和 space 复杂度是多少？

What is the time complexity and space complexity of this algorithm to find Anagrams?

java

algorithm

time-complexity

space-complexity

data-structures