차이 Leetcode 솔루션 찾기

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 구글
알고리즘 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 조회수 24

이 문제에서 우리는 문자열. 두 번째 문자열은 첫 번째 문자열의 문자를 무작위로 섞은 다음 임의의 위치에 추가 문자를 추가하여 생성됩니다. 두 번째 문자열에 추가 된 추가 문자를 반환해야합니다. 문자는 항상 영문 소문자입니다.

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

설명 # 1

문자열에 추가되는 추가 문자 b 문자열로 'f' a 그것을 포함하지 않습니다.

설명 # 2

문자열 동안 4 개의 'a'문자가 있습니다. 따라서 추가 문자는 'a'입니다.

접근 (정렬)

두 문자열을 모두 정렬 한 다음 두 문자열을 문자별로 반복하여 첫 번째 위치를 찾을 수 있습니다. 두 번째 문자열에는 항상 하나가 있습니다. 여분의 캐릭터. 따라서 우리는 항상 문자열이 ab 다릅니다. 그러나 문자열이 b 정렬 후 문자열의 모든 문자와 일치 a 하지만 끝에 하나의 추가 문자가 있습니다. 이 특별한 경우를 처리해야합니다.

차이 Leetcode 솔루션 찾기

암호알고리즘

  1. 두 문자열을 모두 정렬하고 ab. Java에서는 불가능하므로 먼저 다음으로 변환합니다. 문자 배열
  2. 짧은 문자열에있는 모든 문자에 대해 문자 별 검사를 수행합니다.
    • 문자열의 문자가 문자열의 해당 문자와 ​​같지 않음 b:
      • 이 문자를 반환합니다.
  3. 문자열의 마지막 문자를 반환 여분의 캐릭터이기 때문에
  4. 결과 인쇄

차이 찾기 Leetcode 솔루션 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

자바 프로그램

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

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

시간 복잡성

O (NlogN), 여기서 N = 긴 문자열의 길이입니다. O (NlogN) 시간이 걸리는 문자열 / 문자 배열을 정렬합니다.

공간 복잡성

의 위에) 자바에서 O (1) C ++에서 문자열을 char 배열 자바에서.

접근 (해싱)

두 문자열 모두에서 모든 문자를 빈도로 해시하고 빈도가 다른 문자를 찾을 수 있습니다. 우리는 일정한 수의 고유 문자를 가지고 있기 때문입니다. 이 알고리즘은 위에서 설명한 것보다 빠릅니다. 효율적인 구현으로 우리는 해시 테이블 문자열의 모든 문자에 대한 빈도를 증가시킵니다. a 문자열의 모든 문자에 대한 빈도를 줄입니다. b. 이것은 정확히 한 문자의 빈도가 XNUMX이 아닌 그리고 이것은 문자열의 추가 문자가 될 것입니다 b.

암호알고리즘

  1. 모든 문자의 빈도를 다음과 같이 저장하도록 해시 테이블을 초기화하십시오. 주파수
  2. 문자열의 모든 문자 a:
    • 해시 테이블에서 빈도 증가
  3. 문자열의 모든 문자 b:
    • 해시 테이블에서 빈도를 줄입니다.
    • 주파수가 다음과 같으면 -1:
      • 이 캐릭터를 반환
  4. 함수 구문을 유지하려면 '-'반환
  5. 결과 인쇄

차이 찾기 Leetcode 솔루션 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

자바 프로그램

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

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

시간 복잡성

의 위에), N = 문자 빈도를 업데이트하기 위해 두 문자열을 한 번 통과하면서 더 긴 문자열의 크기.

공간 복잡성

O (1). 빈도와 함께 문자를 저장하기 위해 해시 테이블을 사용하지만 입력에 관계없이 일정한 공간을 사용합니다. 따라서 공간 복잡성은 일정합니다.

코멘트를 남겨

Translate »
1