첫 번째 문자열에있는 두 번째 문자열에서 문자 제거

Question

첫 번째 문자열에있는 두 번째 문자열에서 문자를 제거하는 프로그램을 작성했습니다. 복잡성은 BigO (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)); 
    } 
} 

OUTPUT

[x, x, x, c, y, x, x] 

Answer 1

1. 첫 번째 문자열을지도로 변환하십시오. O (N)
2. 다른 문자열 반복 처리 단계에서지도하는 경우 문자 존재를 확인 1. O (N) + O (1)

총 시간 복잡도 = O (N)

여기에 MAP 저장을위한 공간이 추가로 필요합니다.

Answer 2

당신은 (두 번째 문자열에 중복 문자가없는 경우) HashSet의에 두 번째 문자열을 변환하도록 선택할 수 있습니다

. 그런 다음 첫 번째 문자열의 각 문자가 hashmap에 있는지 확인하고 발견되면 제거하십시오.

문자열 배열을 탐색하기위한 O (N) 복잡도와 HashSet에서 put/get의 복잡성은 거의 O (1)입니다.

Answer 3

원본 문자열의 모든 문자가 작은 문자 인 경우 크기가 26 인 부울 배열을 가질 수 있습니다. 그런 다음 원본 문자열을 처음부터 끝까지 검색하고 문자가 있으면 부울 배열을 업데이트합니다. 그런 다음 대상 문자열을 검사하고 부울 배열이 소스 배열에 있는지 여부를 확인합니다.

복잡도는 두 문자열 길이의 합과 같습니다.