从第二个字符串中删除第一个字符串中存在的字符 [英] Remove characters from the second string which are present in the first string

问题描述

我编写了一个程序，从第二个字符串中删除第一个字符串中存在的字符。复杂度为BigO（n ^ 2）。

I have written a program to remove the characters from the second string which are present in the first string. The complexity comes out to be BigO(n^2). Can the complexity be further reduced?

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]

推荐答案

1. 将第一个字符串转换为Map。 O（N）


2. 对其他字符串进行迭代，并检查步骤1中Map中是否存在字符。
   O（N）+ O（1）

总时间复杂度= O（N）

Total time complexity = O(N)

在这里，您需要额外的空间来存储MAP。

Here you have additional space complexity to store MAP.

这篇关于从第二个字符串中删除第一个字符串中存在的字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！