C++LeetCode 구현(97.교차 하 는 문자열)

[LeetCode]97.Interleaving String 이 교차 하 는 문자열
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false
교차 되 는 문자열 과 이전 문자열  Word Break  제 가 전에 말씀 드 린 것 처럼 문자열 의 하위 서열 이나 일치 하 는 문제 가 있 으 면 동적 계획 Dynamic Programming 에 올 라 갑 니 다.다른 것 은 고려 하지 마 세 요.재 귀 하 는 것 은 모두 뜬구름 입 니 다.천신만고 끝 에 귀환 결 과 를 써 서 OJ 에 올 려 놓 은 타 이 밍 Limit Exceed 를 받 으 면 인 기 를 잃 을 수 있 기 때문에 DP 해법 을 직접 고려 하 는 것 이 편리 하 다.일반적으로 문자열 일치 문 제 는 2 차원 dp 배열 을 업데이트 하 는 것 이 고 핵심 은 상태 전이 방정식 을 찾 는 것 이다.그러면 우 리 는 문제 에서 준 예 에서 출발 하여 2 차원 배열 dp 를 수 동 으로 다음 과 같이 쓰 는 것 이 좋 습 니 다.
  Ø d b b c a
Ø T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T
우선,이 문제 의 큰 전 제 는 문자열 s1 과 s2 의 길이 와 s3 와 같 아야 하 는 길이 입 니 다.같 지 않 으 면 false 로 돌아 가 겠 습 니 다.그러면 s1 과 s2 가 빈 문자열 일 때 s3 는 반드시 빈 문자열 이 고 true 로 돌아 갑 니 다.그래서 dp[0][0]에 true 를 직접 부여 한 다음 에 s1 과 s2 중 하 나 를 빈 문자열 로 하면 다른 하 나 는 s3 의 길이 와 같 을 것 이 고 비트 에 따라 비교 합 니 다.만약 에 똑 같 고 이전 위 치 는 True 이 며 true 를 부여 합 니 다.나머지 상황 은 모두 False 를 부여 합 니 다.이러한 2 차원 배열 dp 의 가장자리 가 초기 화 됩 니 다.다음은 상태 이동 방정식 을 찾 아 전체 배열 을 업데이트 하면 됩 니 다.우 리 는 임의의 비 가장자리 위치 dp[i][j]에 있 을 때 왼쪽 이나 위 가 True 또는 False 일 수 있 습 니 다.양쪽 이 모두 업데이트 할 수 있 습 니 다.길 만 있 으 면 이 점 은 True 일 수 있 습 니 다.그러면 우 리 는 왼쪽 이 True 라면 현재 대응 하 는 s2 의 문자열 s2[j-1]와 s3 에 대응 하 는 위치의 문 자 를 제거 해 야 한다.(대응 하 는 위 치 를 계산 할 때 일치 하 는 s1 의 문 자 를 고려 해 야 한다)는 s3[j-1+i]이 고,같 으 면 True 를 부여 하고,반대로 False 를 부여 해 야 한다.위 에 True 인 경우 도 비슷 하기 때문에 상태 전이 방정식 을 구 할 수 있 습 니 다.
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);
그 중에서 dp[i][j]는 s2 의 앞 i 문자 와 s1 의 앞 j 문자 가 s3 의 앞 i+j 문자 와 일치 하 는 지 를 나타 낸다.상기 분석 에 따라 코드 를 다음 과 같이 쓸 수 있다.
해법 1:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1)); 
        dp[0][0] = true;
        for (int i = 1; i <= n1; ++i) {
            dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i <= n2; ++i) {
            dp[0][i] = dp[0][i - 1] && (s2[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);
            }
        }
        return dp[n1][n2];
    }
};

우 리 는 for 순환 을 합 쳐 if 조건 으로 경계 상황 을 처리 할 수 있 습 니 다.전체적인 사고 와 위의 해법 은 큰 차이 가 없습니다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1, false)); 
        for (int i = 0; i <= n1; ++i) {
            for (int j = 0; j <= n2; ++j) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1];
                } else {
                    dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
                }
            }
        }
        return dp[n1][n2];
    }
};

이 문 제 는 최 적 화 된 DFS 를 사용 하여 풀 수 있 습 니 다.우 리 는 HashSet 을 사용 하여 일치 하 는 실패 상황 을 저장 합 니 다.우 리 는 각각 변수 i,j,k 로 문자열 s1,s2,s3 와 일치 하 는 위 치 를 기록 하고 초기 화 할 때 0 으로 전 송 됩 니 다.재 귀 함수 에서 먼저 i 와 j 에 따라 key 값 을 계산 합 니 다.우리 의 HashSet 에 하나의 숫자 만 넣 을 수 있 기 때문에 우 리 는 encode 두 개의 숫자 i 와 j 를 사용 해 야 합 니 다.그래서 i 곱 하기 s3 의 길이 에 j 를 더 해서 key 를 얻 을 수 있 습 니 다.이때 우 리 는 key 가 이미 집합 에 있 으 면 false 로 돌아 가 야 합 니 다.집합 에 저 장 된 것 은 일치 하지 않 는 상황 이기 때 문 입 니 다.그 다음 에 corner case 의 상황 을 먼저 처리 합 니 다.만약 에 i 가 s1 의 길이 와 같다 면 s1 의 문자 가 모두 일치 하 는 것 을 설명 합 니 다.이때 s2 의 남 은 문자 와 s3 의 남 은 문 자 는 직접 일치 할 수 있 기 때문에 우 리 는 이들 이 일치 할 수 있 는 bool 값 을 직접 되 돌려 줍 니 다.마찬가지 로 j 가 s2 의 길이 와 같다 면 s2 의 문자 가 모두 일치 했다 는 것 을 설명 합 니 다.이때 s1 의 남 은 문자 와 s3 의 남 은 문 자 는 직접 일치 할 수 있 기 때문에 우 리 는 이들 이 일치 할 수 있 는 bool 값 을 직접 되 돌려 줍 니 다.s1 과 s2 에 남 은 문자 가 있 으 면 s1 의 현재 문자 가 s3 의 현재 문자 와 같 을 때 재 귀 함 수 를 호출 합 니 다.i 와 k 를 모두 1 로 추가 하고 재 귀 함수 가 true 로 돌아 가면 현재 함수 도 true 로 돌아 갑 니 다.또 다른 상황 은 s2 의 현재 문자 가 s3 의 현재 문자 와 같 을 때 재 귀 함 수 를 호출 하고 j 와 k 가 모두 1 을 더 하면 재 귀 함수 가 true 로 돌아 가면 현재 함수 도 true 로 돌아 갑 니 다.일치 에 실패 하면 키 를 집합 에 넣 고 false 로 돌아 가면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        unordered_set<int> s;
        return helper(s1, 0, s2, 0, s3, 0, s);
    }
    bool helper(string& s1, int i, string& s2, int j, string& s3, int k, unordered_set<int>& s) {
        int key = i * s3.size() + j;
        if (s.count(key)) return false;
        if (i == s1.size()) return s2.substr(j) == s3.substr(k);
        if (j == s2.size()) return s1.substr(i) == s3.substr(k);
        if ((s1[i] == s3[k] && helper(s1, i + 1, s2, j, s3, k + 1, s)) || 
            (s2[j] == s3[k] && helper(s1, i, s2, j + 1, s3, k + 1, s))) return true;
        s.insert(key);
        return false;
    }
};

DFS 가 가능 하 다 면 BFS 도 앉 아 있 지 못 하고 파도 도 쳐 야 한다.여기 서 우 리 는 대기 열 queue 로 연산 을 보조 해 야 합 니 다.만약 에 해법 1 설명 에 있 는 2 차원 dp 배열 에 열 거 된 TF 그림 을 미로 로 삼 으 면 BFS 의 목적 은(0,0)위치 에서 모두 T 의 경 로 를 찾 아(n1,n2)위치 로 가 는 것 입 니 다.여기 서 우 리 는 HashSet 를 사용 해 야 합 니 다.그러나 이 때 는 이미 옮 겨 다 니 는 위치 로 저장 합 니 다.대기 열 에 key 값 이 저장 되 어 있 습 니 다.key 값 의 encode 방법 은 위의 DFS 해법 과 같 습 니 다.초기 에 0 을 넣 습 니 다.그리고 우 리 는 while 순환 을 진행 합 니 다.순환 조건 은 q 가 비어 있 지 않 은 것 을 제외 하고 k 가 n3 보다 작 습 니 다.s3 의 모든 문자 와 일치 하면 끝 납 니 다.그 다음 에 한 층 씩 옮 겨 다 니 기 때문에 quue 의 요소 갯 수 를 직접 순환 해 야 합 니 다.for 순환 에서 팀 의 첫 번 째 요 소 를 디 코딩 하여 i 와 j 값 을 얻 습 니 다.만약 에 i 가 n1 보다 작 으 면 s1 에 남 은 문자 가 있 음 을 설명 합 니 다.만약 에 s1 현재 문자 가 s3 현재 문자 와 같다 면 s1 의 다음 위치 i+1 을 j 와 함께 코드 를 추가 하여 key 값 을 계산 합 니 다.이 key 값 이 집합 에 있 지 않 으 면 집합 에 가입 하고 대기 열 quue 에 가입 합 니 다.마찬가지 로 j 가 n2 보다 작 으 면 s2 에 남 은 문자 가 있다 는 것 을 설명 합 니 다.만약 에 s2 현재 문자 가 s3 현재 문자 와 같다 면 s2 의 다음 위치 j+1 을 i 와 함께 코드 를 추가 하여 key 값 을 계산 합 니 다.만약 에 이 key 값 이 집합 에 있 지 않 으 면 집합 을 추가 하고 대기 열 quue 에 가입 합 니 다.for 순환 이 끝 난 후 k 가 1 증가 합 니 다.마지막 으로 일치 하 는 데 성공 하면 quue 에 하나의(n1,n2)key 값 만 있 을 것 입 니 다.그리고 k 는 이때 n3 와 같 기 때문에 quue 가 비어 있 거나 k 가 n3 와 같 지 않 을 때 false 로 돌아 가 야 합 니 다.코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size(), k = 0;
        unordered_set<int> s;
        queue<int> q{{0}};
        while (!q.empty() && k < n3) {
            int len = q.size();
            for (int t = 0; t < len; ++t) {
                int i = q.front() / n3, j = q.front() % n3; q.pop();
                if (i < n1 && s1[i] == s3[k]) {
                    int key = (i + 1) * n3 + j;
                    if (!s.count(key)) {
                        s.insert(key);
                        q.push(key);
                    }
                }
                if (j < n2 && s2[j] == s3[k]) {
                    int key = i * n3 + j + 1;
                    if (!s.count(key)) {
                        s.insert(key);
                        q.push(key);
                    }
                }
            }
            ++k;
        }
        return !q.empty() && k == n3;
    }
};

C++구현 LeetCode(97.엇 갈 린 문자열)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++엇 갈 린 문자열 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!