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

[LeetCode]161.One Edit 거리 편집 거리
Given two strings s and t, determine if they are both one edit distance apart.
Note: 
There are 3 possiblities to satisify one edit distance apart:

Insert a character into s to get t

Delete a character from s to get t

Replace a character of s to get t

Example 1:
Input: s = "ab", t = "acb" Output: true
Explanation: We can insert 'c' into s to get t.
Example 2:
Input: s = "cab", t = "ad"
Output: false
Explanation: We cannot get t from s by only one step.
Example 3:
Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.
이 문 제 는 이전 문제 입 니 다.  Edit Distance  그러나 이 문 제 는 그 문제 가 어렵 지 않다.이 문 제 는 두 문자열 의 편집 거리 가 1 인지 아 닌 지 를 판단 하 게 한다.그러면 다음 세 가지 상황 으로 나 누 어 고려 하면 된다

1.두 문자열 의 길이 차 이 는 1 보다 크 고 False 로 돌아 갑 니 다.
2.두 문자열 의 길이 차 이 는 1 과 같 습 니 다.긴 문자열 은 한 문 자 를 제거 하고 나머지 는 짧 은 문자열 과 같 아야 합 니 다.
3.두 문자열 의 길이 차 이 는 0 이 고 두 문자열 이 대응 하 는 위치 에 있 는 문 자 는 한 군데 만 다 를 수 있 습 니 다.
모든 상황 을 분석 하면 코드 를 잘 쓸 수 있 습 니 다.다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() < t.size()) swap(s, t);
        int m = s.size(), n = t.size(), diff = m - n;
        if (diff >= 2) return false;
        else if (diff == 1) {
            for (int i = 0; i < n; ++i) {
                if (s[i] != t[i]) {
                    return s.substr(i + 1) == t.substr(i);
                }
            }
            return true;
        } else {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                if (s[i] != t[i]) ++cnt;
            }
            return cnt == 1;
        }
    }
};

우 리 는 실제 적 으로 코드 를 더욱 간결 하 게 쓸 수 있 습 니 다.두 문자열 이 대응 하 는 위치 에 있 는 문 자 를 비교 해 야 합 니 다.만약 에 서로 다른 문자열 을 만 났 을 때 두 문자열 의 길이 관 계 를 볼 수 있 습 니 다.만약 에 같 으 면 현재 위치 뒤의 문자열 이 같 는 지 비교 하고 s 의 길이 가 크 면 s 의 다음 위치 에서 시 작 된 하위 문자열 을 비교 합 니 다.t 의 현재 위치 에서 시 작 된 하위 문자열 과 같 습 니까?반대로 t 의 길이 가 크 면 t 의 다음 위치 에서 시 작 된 하위 문자열 과 s 의 현재 위치 에서 시 작 된 하위 문자열 이 같 습 니까?순환 이 끝나 도 다른 문 자 를 찾 지 못 하면 두 문자열 의 길이 가 1 차이 가 나 는 지 확인 하 십시오.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        for (int i = 0; i < min(s.size(), t.size()); ++i) {
            if (s[i] != t[i]) {
                if (s.size() == t.size()) return s.substr(i + 1) == t.substr(i + 1);
                if (s.size() < t.size()) return s.substr(i) == t.substr(i + 1);
                else return s.substr(i + 1) == t.substr(i);
            }
        }
        return abs((int)s.size() - (int)t.size()) == 1;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/161
유사 한 제목:
Edit Distance
참고 자료:
https://leetcode.com/problems/one-edit-distance/
https://leetcode.com/problems/one-edit-distance/discuss/50108/C%2B%2B-DP
https://leetcode.com/problems/one-edit-distance/discuss/50098/My-CLEAR-JAVA-solution-with-explanation
여기 서 C++LeetCode(161.하나의 편집 거리)실현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++는 하나의 편집 거리 내용 을 실현 합 니 다.우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!