차이 Leetcode 솔루션 찾기


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 구글
해싱

문제 설명

“차이점 찾기”문제에서 우리는 문자열 s 및 t. 문자열 t는 문자열 s의 문자를 무작위로 채우고 임의의 위치에 하나의 문자를 추가하여 생성됩니다.

우리의 임무는 문자열 t에 추가 된 문자를 찾는 것입니다.

s = "abcd", t = "abcde"
e

설명 :

차이 Leetcode 솔루션 찾기

문자열 t의 문자를 다시 정렬하면 "abcde"가됩니다. "abcd"는 이미 문자열 s에 있으므로 t에 추가 된 문자는 "e"입니다.

차이점 찾기 Leetcode 솔루션을위한 정렬 방식

문제를보기 위해 우리의 관점을 바꾸면 때때로 해결하기가 쉬워집니다. 여기서와 같이 문제는 문자열 t가 문자열 s를 섞고 임의의 위치에 하나의 요소를 추가하여 생성된다는 것을 말합니다. 따라서 문자열 s의 임의 위치에 문자를 추가하여 문자열 t가 생성되는 것을 볼 수 있습니다. 이제 문자열 s의 문자가 문자열 t의 문자와 일치하지 않는 위치 만 알아 내면 해당 위치에있는 문자를 반환 할 수 있습니다. 따라서 다음 단계를 따릅니다.

  1. 두 문자열을 모두 정렬하십시오.
  2. 문자열과 일치하지 않는 지점이 추가 된 문자이고 그것이 답입니다.
  3. 모든 문자가 일치하면 문자열 t의 마지막 위치에있는 문자가 답입니다.

실시

차이점 찾기를위한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
    
    sort(t.begin(),t.end());
    
    
    for(int i=0;i<s.length();i++)
    {
      if(s[i]!=t[i])
      {
        return t[i];
      }
    }
    
    return t[t.length()-1];
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

차이점 찾기를위한 Java 코드

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
    char[] sortedS = s.toCharArray();
    char[] sortedT = t.toCharArray();
    Arrays.sort(sortedS);
    Arrays.sort(sortedT);
    for(int i=0;i<s.length();i++){
      if (sortedS[i] != sortedT[i]) {
        return sortedT[i];
      }
    }

    return sortedT[s.length()];
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}
e

차이 찾기 Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (nlogn) 두 문자열을 모두 정렬하고 있기 때문입니다. 여기서 n은 주어진 문자열 s의 길이입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (N) 자바 솔루션의 경우 문자열을 배열로 변환하지만 C ++의 경우 sting의 내부 정렬을 허용하기 때문에 O (1)입니다.

차이점 찾기 Leetcode 솔루션을위한 해싱 접근법

다음 단계를 따릅니다.

  1. 문자의 빈도를 저장하기 위해 크기가 26 인 빈도 배열을 만듭니다. 0으로 초기화합니다.
  2. 문자열 s를 순회하고 주파수 배열에 문자의 빈도를 저장합니다.
  3. 이제 문자열 t를 순회하고 주파수 배열에서 문자열 t를 순회하는 동안 만나는 각 문자의 빈도를 줄입니다.
  4. 마지막으로 주파수 배열을 가로 지르면 값이 XNUMX 인 위치에 해당하는 문자가 추가 된 문자이며 이것이 필수 답변입니다.

실시

차이점 찾기를위한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
      char findTheDifference(string s, string t) {
        int count[26] = {0};
        for(int i=0;i<s.length();i++) count[s[i]-'a']++;
        for(int i=0;i<t.length();i++) count[t[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return 'a';
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

차이점 찾기를위한 Java 코드

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
        int[] count = new int[26];
        char[] S = s.toCharArray(), T = t.toCharArray();
        for(int i=0;i<S.length;i++) count[S[i]-'a']++;
        for(int i=0;i<T.length;i++) count[T[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return '\0';
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}
e

차이 찾기 Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (N) 문자열을 한 번만 통과하기 때문입니다. 여기서 n은 주어진 문자열의 길이입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 주파수 배열에 일정한 공간을 사용하기 때문입니다.

참조