가장 긴 회문 부분 문자열 LeetCode 솔루션


자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance Facebook 구글 인포시스 링크드 인 Microsoft 신탁 세일즈 포스 테슬라 월마트 연구소 웨이 페어 Yahoo 조호 (Zoho)
리트코드 LeetCodeSolutions Tik의 톡조회수 54

문제 정책

또한 가장 긴 회문 부분 문자열 LeetCode 솔루션 – "가장 긴 회문 부분 문자열"은 문자열 s가 주어지면 s에서 가장 긴 회문 부분 문자열을 반환한다고 말합니다.

참고: 회문은 앞으로 읽어도 뒤로 읽어도 같은 단어입니다(예: 부인).

예:

가장 긴 회문 부분 문자열 LeetCode 솔루션

 

s = "babad"
"bab"

설명 :

모든 독특한 회문 부분 문자열 "b", "a", "d", "bab", "aba"입니다.

그 중 '밥'과 '아바'는 가장 긴 부분 문자열.

s = "cbbd"
"bb"

설명 :

모든 고유 회문 하위 문자열은 "c", "b", "d", "bb"입니다.

이 중 "bb"는 가장 긴 부분 문자열.

무차별 대입 솔루션

아이디어 :

찾으시는 제품/부품의 모델번호 또는 사진을 보내주세요. 모든 하위 문자열을 확인하고 어떤 하위 문자열이 회문인지 확인, 다음 중 가장 오래 걸립니다. 

암호:

가장 긴 회문 부분 문자열 LeetCode 솔루션의 C++ 프로그램

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

bool check(string &s, int i, int j)
{
    while (i <= j)
    {
        if (s[i] != s[j])
        {
            return false;
        }
        i++, j--;
    }
    return true;
}
string longestPalindrome(string s)
{
    int n = s.length();
    int max_len = 0;
    int starting_index = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            if (check(s, i, j))
            {
                if (j - i + 1 > max_len)
                {
                    max_len = j - i + 1;
                    starting_index = i;
                }
            }
        }
    }
    return s.substr(starting_index, max_len);
}
int main()
{
    string s = "babad";
    cout << longestPalindrome(s) << endl;
    return 0;
}

 

bab

가장 긴 회문 부분 문자열 LeetCode 솔루션의 JAVA 프로그램

public class TutorialCup {
    public static Boolean check(String s, int i, int j) {
        while (i <= j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    public static String longestPalindrome1(String s) {
        int n = s.length();
        int max_len = 0;
        int starting_index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (check(s, i, j)) {
                    if (j - i + 1 > max_len) {
                        max_len = j - i + 1;
                        starting_index = i;
                    }
                }
            }
        }
        return s.substring(starting_index, starting_index + max_len);
    }

    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindrome(s));
    }
}
bab

복잡성 분석

시간 복잡성

위 코드의 시간 복잡도는 O(n^3)입니다. 왜냐하면 우리는 모든 하위 문자열을 순회한 다음 각 하위 문자열이 회문인지 여부를 확인하기 때문입니다. n^2개의 하위 문자열이 있고 하위 문자열을 확인하는 데 O(n) 시간이 걸리므로 총 시간 복잡도는 O(n^3)입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 추가 공간을 사용하지 않기 때문입니다.

최적화된 솔루션

아이디어 :

아이디어는 다시 동일합니다. 모든 부분 문자열에 대해 회문인지 확인 여부, 그리고 만약 그렇다면 우리는 그들 중에서 가장 오래 걸릴 것입니다. 유일한 변경 사항은 이제 부분 문자열이 회문이든 아니든 "dp" 배열에서. 

이제 시작 인덱스가 "i"이고 끝 인덱스가 "j"인 부분 문자열이 회문인지 확인하려면 두 가지 조건만 확인하면 됩니다.

  1.  i번째와 j번째 문자의 경우 문자열이 같음의 메이크업 시연, 그리고 한국에서 사랑을 담아 보낸  
  2. 시작 인덱스가 i+1이고 끝 인덱스가 j-1인 부분 문자열은 회문입니다.

위의 두 조건이 모두 참이면 이 하위 문자열도 회문임을 의미합니다. 

암호:

가장 긴 회문 부분 문자열의 C++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> &dp, int i, int j, string &s)
{
    if (dp[i][j] != -1)
    {
        return dp[i][j];
    }
    dp[i][j] = 0;
    if (i == j)
    {
        return dp[i][j] = 1;
    }
    if (j - i == 1)
    {
        if (s[i] == s[j])
        {
            return dp[i][j] = 1;
        }
        else
        {
            return dp[i][j];
        }
    }
    if (s[i] == s[j] && solve(dp, i + 1, j - 1, s) == 1)
    {
        return dp[i][j] = 1;
    }
    return dp[i][j];
}
string longestPalindrome(string s)
{
    int n = s.length();
    int max_len = 0;
    int starting_index = 0;
    vector<vector<int>> dp(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            solve(dp, i, j, s);
            if (dp[i][j] == 1)
            {
                if (j - i + 1 > max_len)
                {
                    max_len = j - i + 1;
                    starting_index = i;
                }
            }
        }
    }
    return s.substr(starting_index, max_len);
}
int main()
{
    string s = "babad";
    cout << longestPalindrome(s) << endl;
    return 0;
}
bab

의 JAVA 프로그램 가장 긴 회문 부분 문자열

public class TutorialCup {
    public static int solve(int[][] dp, int i, int j, String s) {
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        dp[i][j] = 0;
        if (i == j) {
            return dp[i][j] = 1;
        }
        if (j - i == 1) {
            if (s.charAt(i) == s.charAt(j)) {
                return dp[i][j] = 1;
            } else {
                return dp[i][j];
            }
        }
        if (s.charAt(i) == s.charAt(j) && solve(dp, i + 1, j - 1, s) == 1) {
            return dp[i][j] = 1;
        }
        return dp[i][j];
    }

    public static String longestPalindrome(String s) {
        int n = s.length();
        int max_len = 0;
        int starting_index = 0;
        int dp[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                solve(dp, i, j, s);
                if (dp[i][j] == 1) {
                    if (j - i + 1 > max_len) {
                        max_len = j - i + 1;
                        starting_index = i;
                    }
                }
            }
        }
        return s.substring(starting_index, starting_index + max_len);
    }

    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindrome(s));
    }
}

 

bab

복잡성 분석

시간 복잡성

위 코드의 시간 복잡도는 O(n^2)입니다. 왜냐하면 우리는 모든 부분 문자열을 순회하기 때문입니다. 회문인 경우 각 부분 문자열 확인 아니면. n^2개의 하위 문자열이 있고 하위 문자열을 확인하는 데 O(1) 시간이 걸리므로 총 시간 복잡도는 O(n^2)입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (n ^ 2) 하위 문자열이 회문인지 여부를 저장하는 dp 배열을 사용하고 있기 때문입니다.

참고 https://en.wikipedia.org/wiki/Palindrome

코멘트를 남겨

Translate »
3