这个算法的时间复杂度和空间复杂度是多少来寻找Anagram

Question

我正在处理亚马逊软件的一个面试问题
问题是
"设计一种算法，以获取字符串列表和单个输入字符串，并返回列表的索引，这些索引是输入字符串的变位符，而不考虑特殊字符。"
我能够很好地设计算法，我在psuedo代码中所做的是
1.创建单个输入字符串的数组字符计数
2.对于列表中的每个字符串，构造一个数组字符计数
3.将列表中每个字符串的字符数与单个输出字符串进行比较
4.如果相同，则将其添加到包含变位词所有索引的列表中
5.返回索引列表。

以下是我在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;
}

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

Answer 1

因为我正在创建26长度数组的N个副本，所以空间复杂性会是O（N）吗？

是的。

时间复杂度算法是否只是O（N），其中N是列表的大小

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