One Edit Distance

2020-07-07  本文已影响0人  瞬铭

https://leetcode.com/problems/one-edit-distance/
给定word1,word2 计算从是否可以一步从word1变到word2
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比较类似,但是不用那么复杂把最小Distance求出,只用遵循规则计算是否一步能到

    public Boolean isOneEditDistance(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();

        if ((Math.abs(sLen - tLen) > 1)) {
            return false;
        }

        if (sLen > tLen) {
            return isOneEditDistance(s.substring(0, sLen - 1), t);
        } else if (sLen < tLen) {
            return isOneEditDistance(s, t.substring(0, t.length() - 1));
        }
        return s.equals(t) ? true : isOneEditDistance(s.substring(0, sLen - 1), t.substring(0, t.length() - 1));
    }
上一篇下一篇

猜你喜欢

热点阅读