하위 시퀀스 Leetcode 솔루션입니다

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 블룸버그 게시물에서 Facebook 구글 Microsoft 클립 Yandex 주차
알고리즘 코딩 동적 프로그래밍 탐욕스러운 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 조회수 30

문제 정책

이 문제에서 우리는 두 가지 다른 문자열. 목표는 첫 번째 문자열이 하위 시퀀스 두 번째.

first string = "abc"
second string = "mnagbcd"
true
first string = "burger"
second string = "dominos"
false

하위 시퀀스 Leetcode 솔루션입니다

접근 (재귀)

이것은 우리가 그들의 끝에서 문자열 일치를 시작할 수 있다는 것을 쉽게 알 수 있습니다. 문자열의 마지막에있는 문자가 일치하면 원래 문자열에서 얻을 수있는 두 문자열을 찾을 수있는 하위 문제가 줄어 듭니다. 시간 내에 마지막 문자를 삭제하면 하위 시퀀스 기준을 따릅니다. 끝 문자가 일치하지 않으면 두 번째 문자열의 마지막 문자 만 삭제하여 앞을 검색합니다.

이것은 문자열의 인덱스를 매개 변수로 전달하여 모든 재귀 호출에서 문자를 비교함으로써 재귀 적으로 수행 할 수 있습니다.

암호알고리즘

  1. 색인 첫 번째 문자열의 마지막 색인을 나타내고재귀 호출에서 두 번째 문자열의 마지막 인덱스를 나타냅니다.
  2. If 나는 == -1:
    1. 첫 번째 문자열을 완전히 탐색했습니다. 참된
  3. If j == -1:
    1. 첫 번째 문자열을 완전히 탐색했습니다. 그릇된
  4. If first_string [i] == second_string [j] :
    1. 인덱스로 재귀 함수 호출 (i – 1, j – 1)
  5. 인덱스가있는 재귀 함수의 결과를 반환합니다. (i, j – 1)

Is Subsequence Leetcode 솔루션 구현

C ++ 프로그램

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

string S , T;

bool checkSubsequence(int i , int j)
{
    if(i == -1)
        return true;
    if(j == -1)
        return false;
    if(S[i] == T[j])
        return checkSubsequence(i - 1 , j - 1);
    return checkSubsequence(i , j - 1);
}

bool isSubsequence(string s, string t)
{
    S = s , T = t;
    return checkSubsequence((int)s.size() - 1 , (int)t.size() - 1);
}

int main()
{
    string s = "abc";
    string t = "mnagbcd";

    cout << (isSubsequence(s , t) ? "true" : "false") << '\n';
    return 0;
}

자바 프로그램

class is_subsequence
{
    static String S , T;

    public static void main(String args[])
    {
        String a = "abc" , b = "mnagbcd";
        System.out.println((isSubsequence(a , b) ? "true" : "false"));
    }

    static boolean checkSubsequence(int i , int j)
    {
        if(i == -1)
            return true;
        if(j == -1)
            return false;
        if(S.charAt(i) == T.charAt(j))
            return checkSubsequence(i - 1 , j - 1);
        return checkSubsequence(i , j - 1);
    }

    static boolean isSubsequence(String s, String t)
    {
        S = s;
        T = t;
        return checkSubsequence((int)s.length() - 1 , (int)t.length() - 1);
    }
}
true

Is Subsequence Leetcode 솔루션의 복잡성 분석

시간 복잡성

O (분 (N, M)) 문자열 중 하나가 순회 될 때까지 반복해야하기 때문입니다. NM 문자열의 길이입니다.

공간 복잡성

O (분 (M, N) 재귀 호출로 인해 최악의 경우.

접근 방식 (두 포인터)

두 개의 포인터를 유지하여 위의 기술을 반복적으로 사용할 수 있습니다. i각 문자열의 마지막 인덱스를 저장합니다. 둘 중 하나가 XNUMX이 될 때까지 반복 할 수 있습니다. 만약 i (첫 번째 문자열의 포인터)는 0보다 크거나 같으며 첫 번째 문자열을 완전히 탐색 할 수 없었으므로 두 번째 문자열의 하위 시퀀스가 ​​아닙니다. 그렇지 않으면 true를 반환합니다.

암호알고리즘

  1. 두 포인터 초기화 i와 j 두 문자열의 마지막 인덱스를 저장합니다.
  2. DaVinci에는 i> = 0 및 j> = 0 :
    1. first_string [i] == second_string [j] 인 경우 :
      1. i—, j-
    2. 다른
      1. j-
  3. If i > = 0 :
    1. 반품 그릇된
  4. 반품 참된

Is Subsequence Leetcode 솔루션 구현

C ++ 프로그램

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

string S , T;

bool isSubsequence(string s , string t)
{
    int i = s.size() , j = t.size();

    i-- , j--;

    while(i >= 0 && j >= 0)
    {
        if(s[i] == t[j])
            i-- , j--;
        else
            j--;
    }

    if(i >= 0)
        return false;
    return true;
}

int main()
{
    string s = "abc";
    string t = "mnagbcd";

    cout << (isSubsequence(s , t) ? "true" : "false") << '\n';
    return 0;
}

자바 프로그램

class is_subsequence
{
    static String S , T;

    public static void main(String args[])
    {
        String a = "abc" , b = "mnagbcd";
        System.out.println((isSubsequence(a , b) ? "true" : "false"));
    }

    static boolean isSubsequence(String s , String t)
    {
        int i = s.length() , j = t.length();

        i--;
        j--;

        while(i >= 0 && j >= 0)
        {
            if(s.charAt(i) == t.charAt(j))
            {
                i--;
                j--;
            }
            else
                j--;
        }

        if(i >= 0)
            return false;
        return true;
    }
}
true

Is Subsequence Leetcode 솔루션의 복잡성 분석

시간 복잡성

O (분 (M, N)) 우리는 i 또는 j XNUMX이됩니다. M과 N은 문자열의 길이입니다.

공간 복잡성

O (1) 메모리에서 일정한 공간을 사용하기 때문입니다.

코멘트를 남겨

Translate »
1