C++LeetCode 구현(87.문자열 교란)

10720 단어 C++교란 문자열LeetCode
[LeetCode]87.스 크 램 블 문자열 흐 트 러 짐
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
    great
/    \
gr    eat
/ \    /  \
g   r  e   at
/ \
a   t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
    rgeat
/    \
rg    eat
/ \    /  \
r   g  e   at
/ \
a   t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
    rgtae
/    \
rg    tae
/ \    /  \
r   g  ta  e
/ \
t   a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
이 문 제 는 하나의 문자열 을 이 진 트 리 의 뿌리 로 삼 은 다음 빈 문자열 이 아 닌 하위 노드 라 고 정의 한 다음 에 어떤 하위 문자열 의 두 하위 노드 를 교환 하고 다시 기어 가서 새로운 문자열 을 만 듭 니 다.이 새 문자열 은 원래 문자열 과 서로 어 지 럽 히 는 문자열 입 니 다.이 문 제 는 재 귀 Recursion 또는 동적 계획 Dynamic Programming 으로 풀 수 있 습 니 다.우 리 는 먼저 재 귀 하 는 해법 을 살 펴 보 겠 습 니 다.쉽게 말 하면 s1 과 s2 가 scramble 이 라면 s1 에 있 는 길이 l1 이 반드시 존재 하고 s1 을 s11 과 s12 로 나 누 어 똑 같이 s21 과 s22 가 있 습 니 다.그러면 s11 과 s21 은 scramble 이 고 s12 와 s22 는 scramble 이다.아니면 s11 과 s22 는 스 크 램 블 이 고 s12 와 s21 은 스 크 램 블 입 니 다.제목 의 예 를 들 어 rgeat 와 great 에 있어 rgeat 는 rg 와 eat 두 단락 으로 나 눌 수 있 고 great 는 gr 과 eat 두 단락 으로 나 눌 수 있 으 며 rg 와 gr 은 scrambled 이 고 eat 와 eat 는 당연히 scrambled 이다.이 점 에 근거 하여 우 리 는 코드 를 다음 과 같이 쓸 수 있다.
해법 1:

// Recursion
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        string str1 = s1, str2 = s2;
        sort(str1.begin(), str1.end());
        sort(str2.begin(), str2.end());
        if (str1 != str2) return false;
        for (int i = 1; i < s1.size(); ++i) {
            string s11 = s1.substr(0, i);
            string s12 = s1.substr(i);
            string s21 = s2.substr(0, i);
            string s22 = s2.substr(i);
            if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
            s21 = s2.substr(s1.size() - i);
            s22 = s2.substr(0, s1.size() - i);
            if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
        }
        return false;
    }
};
물론 이 문 제 는 다이나믹 프로 그래 밍 을 동적 으로 기획 할 수도 있다.기 존의 경험 에 따 르 면 뿌리 문자열 과 관련 된 문 제 는 십중팔구 DP 로 풀 수 있다.그러면 어 려 운 점 은 상태 이동 방정식 을 어떻게 찾아내 느 냐 에 있다.이것 은 3 차원 동적 계획 의 제목 입 니 다.3 차원 배열 dp[i][j][n]을 사용 합 니 다.그 중에서 i 는 s1 의 시작 문자 이 고 j 는 s2 의 시작 문자 이 며 n 은 현재 문자열 의 길이 입 니 다.dp[i][j][len]은 i 와 j 가 각각 s1 과 s2 기점 의 길 이 를 len 으로 하 는 문자열 이 서로 scramble 인지 아 닌 지 를 나타 냅 니 다.dp 배열 이 있 으 면 상태 전이 방정식 을 보 세 요.즉,역사 정보 에 따라 dp[i][j][len]을 어떻게 얻 는 지 보 세 요.이것 이 만족 하 는 지 아 닌 지 를 판단 하 는 것 은 먼저 현재 s1[i+len-1]문자열 을 한 칼 에 두 부분 으로 나 눈 다음 에 두 가지 상황 으로 나 누 는 것 이다.첫 번 째 는 왼쪽 과 s2[j...j+len-1]왼쪽 부분 이 scramble 인지,그리고 오른쪽 과 s2[j...j+len-1]오른쪽 부분 이 scramble 인지 아 닌 지 를 판단 하 는 것 이다.두 번 째 상황 은 왼쪽 과 s2[j...j+len-1]오른쪽 부분 이 scramble 인지,오른쪽 과 s2[j...j+len-1]왼쪽 부분 이 scramble 인지 아 닌 지 입 니 다.만약 상기 두 가지 상황 이 성립 된다 면 s1[i+len-1]과 s2[j...j+len-1]은 scramble 의 것 임 을 설명 한다.그리고 이러한 좌우 부분 이 스 크 램 블 인지 아 닌 지 를 판단 하 는 데 역사적 인 정보 가 있 습 니 다.길이 가 n 보다 작은 모든 상황 이 앞에서 해결 되 었 기 때 문 입 니 다(즉,길이 가 가장 바깥쪽 순환 입 니 다).위 에서 말 한 것 은 칼 을 쪼 개 는 상황 입 니 다.s1[i+len-1]에 대해 len-1 가지 쪼 개 는 방법 이 있 습 니 다.이런 쪼 개 는 방법 중 하나 만 성립 되면 두 꼬치 는 scramble 입 니 다.정리 해 보면 상태 전이 방정식 은:
dp[i][j][len] = || (dp[i][j][k] && dp[i+k][j+k][len-k] || dp[i][j+len-k][k] && dp[i+k][j][len-k])
모든 1<=k해법 2:

// DP
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        int n = s1.size();
        vector<vector<vector<bool>>> dp (n, vector<vector<bool>>(n, vector<bool>(n + 1)));
        for (int len = 1; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                for (int j = 0; j <= n - len; ++j) {
                    if (len == 1) {
                        dp[i][j][1] = s1[i] == s2[j];
                    } else {
                        for (int k = 1; k < len; ++k) {
                            if ((dp[i][j][k] && dp[i + k][j + k][len - k]) || (dp[i + k][j][len - k] && dp[i][j + len - k][k])) {
                                dp[i][j][len] = true;
                            }
                        }
                    }                
                }
            }
        }
        return dp[0][0][n];
    }
};
위의 코드 의 실현 과정 은 다음 과 같다.먼저 하나의 문자 로 비교 하여 그들 사이 가 scrambled 인지 아 닌 지 를 판단 한다.두 번 째 표 의 첫 번 째 값(gr 과 rg 가 scrambled 인지 아 닌 지)을 업데이트 할 때 첫 번 째 표 의 두 가지 구성 을 비교 했다.하 나 는 g 와 r,r 와 g 이 고 다른 하 나 는 g 와 g,r 와 r 이다.그 중에서 후 자 는 진실 이 고 그 중 하 나 를 진실 이 라면 이 값 을 진실 으로 부여 한다.사실 이 원 리 는 이전 재 귀적 원리 와 매우 비슷 하 다.어떤 두 문자열 이 scrambled 인지 판단 할 때 가능 한 모든 분할 방법의 하위 문자열 이 scrambled 인지 비교 하고 하나의 분할 방법 이 진실 이 라면 비교 하 는 두 문자열 은 반드시 scrambled 이다.rge 와 gre 의 실현 과정 을 비교 하면 다음 과 같다.
     r    g    e
g    x    √    x
r    √    x    x
e    x    x    √
rg    ge
gr    √    x
re    x    x
rge
gre   √
DP 의 또 다른 표기 법,다른 문장 을 참고 하 다사고방식 이 모두 같 습 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

// Still DP
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        int n = s1.size();
        vector<vector<vector<bool>>> dp (n, vector<vector<bool>>(n, vector<bool>(n + 1)));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                for (int k = 1; k <= n - max(i, j); ++k) {
                    if (s1.substr(i, k) == s2.substr(j, k)) {
                        dp[i][j][k] = true;
                    } else {
                        for (int t = 1; t < k; ++t) {
                            if ((dp[i][j][t] && dp[i + t][j + t][k - t]) || (dp[i][j + k - t][t] && dp[i + t][j][k - t])) {
                                dp[i][j][k] = true;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }
};
다음 과 같은 해법 은 첫 번 째 해법 의 사고방식 과 같 습 니 다.정렬 알고리즘 을 사용 하지 않 고 구조 어 를 구 하 는 것 과 유사 한 방법 을 사 용 했 습 니 다.한 배열 로 모든 자모 가 나타 나 는 횟수 를 저장 하고 그 다음 에 Scramble 문자열 을 판단 하 는 방법 은 이전 과 다 르 지 않 습 니 다.
해법 4:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1 == s2) return true;
        if (s1.size() != s2.size()) return false;
        int n = s1.size(), m[26] = {0};
        for (int i = 0; i < n; ++i) {
            ++m[s1[i] - 'a'];
            --m[s2[i] - 'a'];
        }
        for (int i = 0; i < 26; ++i) {
            if (m[i] != 0) return false;
        }
        for (int i = 1; i < n; ++i) {
            if ((isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) || (isScramble(s1.substr(0, i), s2.substr(n - i)) && isScramble(s1.substr(i), s2.substr(0, n - i)))) {
                return true;
            }
        }
        return false;
    }
};
아래 의 이러한 해법 은 실제 적 으로 해법 2 의 재 귀 형식 이다.우 리 는 memo 배열 로 대량의 연산 을 줄 였 다.이곳 의 memo 배열 은 반드시 세 가지 상태 가 있어 야 한다.초기 화 는-1 이 고 구역 내 는 scramble 은 1 이 며 scramble 이 아니 라 0 이다.그러면 이미 특정한 구간 을 계산 한 것 을 피 할 수 있 지만 scramble 이 아니 기 때문에 다시 한 번 계산 을 한다.코드 는 다음 과 같 습 니 다.
해법 5:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1 == s2) return true;
        if (s1.size() != s2.size()) return false;
        int n = s1.size();
        vector<vector<vector<int>>> memo(n, vector<vector<int>>(n, vector<int>(n + 1, -1)));
        return helper(s1, s2, 0, 0, n, memo);
    }
    bool helper(string& s1, string& s2, int idx1, int idx2, int len, vector<vector<vector<int>>>& memo) {
        if (len == 0) return true;
        if (len == 1) memo[idx1][idx2][len] = s1[idx1] == s2[idx2];
        if (memo[idx1][idx2][len] != -1) return memo[idx1][idx2][len];
        for (int k = 1; k < len; ++k) {
            if ((helper(s1, s2, idx1, idx2, k, memo) && helper(s1, s2, idx1 + k, idx2 + k, len - k, memo)) || (helper(s1, s2, idx1, idx2 + len - k, k, memo) && helper(s1, s2, idx1 + k, idx2, len - k, memo))) {
                return memo[idx1][idx2][len] = 1;
            }
        }
        return memo[idx1][idx2][len] = 0;
    }
};
C++구현 LeetCode(87.교란 문자열)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 교란 문자열 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!
C++LeetCode 구현(86.링크 구분)
C++파일 을 재 귀적 으로 옮 겨 다 니 며 MD5 의 인 스 턴 스 코드 를 계산 합 니 다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage