C++LeetCode 구현(72.편집 거리)

[LeetCode]72.거리 편집 거리 편집
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:

Insert a character

Delete a character

Replace a character

Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
이 문 제 는 하나의 문자열 에서 다른 문자열 로 전환 하 는 데 필요 한 변환 절 차 를 구 합 니 다.모두 세 가지 변환 방식 이 있 습 니 다.한 문 자 를 삽입 하고 한 문 자 를 삭제 하 며 한 문 자 를 교체 합 니 다.제목 은 언뜻 보기 에는 어렵 지 않 지만 실제로는 현묘 함 을 숨 기 고 있다.두 문자열 을 비교 할 때 보통 HashMap 으로 문자 가 나타 나 는 빈 도 를 계산 하 는 것 을 고려 하지만 이 문 제 는 이렇게 할 수 없다.문자열 의 순서 가 중요 하기 때문이다.또 하나의 흔히 볼 수 있 는 오 류 는 길이 가 다른 두 문자열 에 대해 길이 의 차 이 는 모두 삽입 작업 을 한 다음 에 모든 문자 에 대응 하고 서로 다른 부분 은 수정 작업 을 해 야 한다 고 생각 하 는 것 이다.그러나 사실은 이렇게 하면 조작 을 많이 할 수 있다.삭제 작업 은 때때로 수정 효 과 를 얻 을 수 있 기 때문이다.예 를 들 어 제목 의 예 1 은 horse 를 rorse 로 바 꾼 후에 두 번 째 r 를 삭제 하고 마지막 e 와 함께 ros 로 바 꿀 수 있다.실제로 세 단계 만 있 으 면 완성 된다.어떤 자 모 를 삭제 한 후 원래 좌우 로 연결 되 지 않 았 던 자모 가 지금 은 연결 되 어 있어 필요 한 문자열 을 만 들 수 있 기 때문이다.그래서 비교 할 때 세 가지 조작 을 시도 해 야 한다.왜냐하면 현재 의 조작 이 뒤에 어떤 영향 을 미 칠 지 아무 도 모 르 기 때문이다.현재 비교 되 고 있 는 두 글자 에 대해 word1[i]과 word2[j]는 둘 이 같 으 면 모든 것 을 말 할 수 있 고 바로 다음 위치 로 넘 어 갑 니 다.다 르 면 세 가지 처리 방법 이 있 습 니 다.먼저 워드 2[j]를 직접 삽입 하면 워드 2[j]위치의 문 자 는 건 너 뛰 고 워드 1[i]과 워드 2[j+1]를 비교 하면 됩 니 다.두 번 째 방법 은 삭제 입 니 다.곧 word1[i]문 자 를 직접 삭제 할 것 입 니 다.이어서 word1[i+1]과 word2[j]를 비교 하면 됩 니 다.세 번 째 는 워드 1[i]을 워드 2[j]로 수정 한 다음 에 워드 1[i+1]과 워드[j+1]을 비교 하면 된다.여기까지 분석 하면 재 귀적 인 코드 를 직접 쓸 수 있 지만 안 타 깝 게 도 Time Limited Exceed 를 사용 하기 때문에 시간 복잡 도 를 최적화 시 켜 야 합 니 다.대량의 중복 계산 을 제거 해 야 합 니 다.여 기 는 메모리 배열 memo 를 사용 하여 계 산 된 상 태 를 저장 하고 OJ 를 통 해 이곳 의 insertCnt,deleteCnt 를 주의 할 수 있 습 니 다.replaceCnt 는 현재 대응 하 는 위치 가 각각 삽입,삭제,교체 작업 을 사 용 했 음 을 나타 내 는 것 일 뿐 전체 반환 의 최소 거 리 를 표시 합 니 다.뒤의 위 치 는 재 귀 를 최소 로 호출 합 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> memo(m, vector<int>(n));
        return helper(word1, 0, word2, 0, memo);
    }
    int helper(string& word1, int i, string& word2, int j, vector<vector<int>>& memo) {
        if (i == word1.size()) return (int)word2.size() - j;
        if (j == word2.size()) return (int)word1.size() - i;
        if (memo[i][j] > 0) return memo[i][j];
        int res = 0;
        if (word1[i] == word2[j]) {
            return helper(word1, i + 1, word2, j + 1, memo);
        } else {
            int insertCnt = helper(word1, i, word2, j + 1, memo);
            int deleteCnt = helper(word1, i + 1, word2, j, memo);
            int replaceCnt = helper(word1, i + 1, word2, j + 1, memo);
            res = min(insertCnt, min(deleteCnt, replaceCnt)) + 1;
        }
        return memo[i][j] = res;
    }
};

기 존의 경험 에 따 르 면 문자열 과 관련 된 문제 와 극치 의 문 제 는 십중팔구 동적 계획 Dynamic Programming 으로 풀 었 는데 이 문제 도 예 외 는 아니다.사실 해법 1 의 재 귀적 기억 배열 의 방법 도 DP 의 재 귀적 표기 법 으로 볼 수 있다.2 차원 배열 dp 를 유지 해 야 합 니 다.크기 는 mxn 이 고 m 와 n 은 각각 워드 1 과 워드 2 의 길이 입 니 다.dp[i][j]는 워드 1 의 앞 i 문자 에서 워드 2 의 앞 j 문자 로 전환 하 는 데 필요 한 절 차 를 나타 낸다.먼저 이 2 차원 배열 dp 의 첫 번 째 줄 에 값 을 부여 합 니 다.이것 은 매우 간단 합 니 다.첫 번 째 줄 과 첫 번 째 열 에 대응 하 는 문자열 이 모두 빈 문자열 이기 때문에 전환 절 차 는 완전히 다른 문자열 의 길이 입 니 다.기 존의 DP 문제 와 유사 하 게 어 려 운 점 은 상태 전이 방정식 을 찾 는 것 입 니 다.예 를 들 어 워드 1 은'bbc'이 고 워드 2 는'abcd'이 며 dp 배열 은 다음 과 같 습 니 다.
  Ø a b c d
Ø 0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2
관찰 을 통 해 알 수 있 듯 이 워드 1[i]=워드 2[j]시 dp[i][j]=dp[i-1][j-1],다른 상황 에서 dp[i][j]는 왼쪽,왼쪽,위의 세 가지 값 중 최소 값 에 1 을 더 한 것 이다.사실은 이곳 의 왼쪽,위,왼쪽 위 에 각각 대응 하 는 증가,삭제,수정 작업 은 해법 의 설명 부분 을 구체 적 으로 참조 할 수 있다.그러면 상태 전이 방정식 을 얻 을 수 있다.
dp[i][j] =      /    dp[i - 1][j - 1]                                                                   if word1[i - 1] == word2[j - 1]
                  \    min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1            else
해법 2:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int i = 0; i <= n; ++i) dp[0][i] = i;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

여기 서 C++LeetCode(72.편집 거리)실현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++편집 거리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!