我已经编写了一个程序来删除第一个字符串中第二个字符串中的字符。复杂度为双(n ^ 2)。复杂性会进一步降低吗?

public class Tmp {

    public static void main(String[] args) {
        String s = "halloween";
        String s1 = "halcyon";
        char[] ss = s.toCharArray();
        char[] ss1 = s1.toCharArray();

        for(int i=0;i<ss.length;i++){
          for(int j=0;j<ss1.length;j++){
                if(ss1[j] == ss[i]){
                    ss1[j] = 'x'; //Replace the common char with x
                }
            }
         }
        System.out.println(Arrays.toString(ss1));
    }
}

输出
 [x, x, x, c, y, x, x]

最佳答案

将第一个字符串转换为映射。O(N)
在其他字符串上迭代并检查步骤1的映射中是否存在字符。
O(N)+O(1)
总时间复杂度=O(n)
这里有额外的空间复杂度来存储地图。

10-06 05:08
查看更多