`

Leetcode - One Edit Distance

 
阅读更多
[分析]
两字符串相同或者长度差异大于等于2都不符合要求,只需要检查那些长度相同或者相差为1的情况。逐个字符检查,发现第一个差异字符,若s和t长度相等将s中字符替换为t中字符,若不等则在s中插入t当前字符,然后跳出检查循环。若检查过程无差异字符(说明长度差1)或者消除发现的第一个差异后两字符串相等说明两字符串编辑距离为1.
这个思路和实现参考https://leetcode.com/discuss/42379/4ms-11-lines-c-solution-with-explanations,自己写的丑代码就不粘贴了

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s == null || t == null || s.equals(t)) return false;
        int sLen = s.length(), tLen = t.length();
        if (sLen > tLen) return isOneEditDistance(t, s);
        if (sLen + 1 < tLen) return false; // |sLen - tLen| >= 2
        
        boolean misMatch = false;
        for (int i = 0; i < sLen; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (sLen == tLen) {// replace the first diff char is s with char of t
                    s = s.substring(0, i) + t.charAt(i) + s.substring(i + 1, sLen);
                } else { // insert curr char of t
                    s = s.substring(0, i) + t.charAt(i) + s.substring(i, sLen);
                }
                misMatch = true;
                break;
            }
        }
        return !misMatch || s.equals(t);
    }
}
分享到:
评论

相关推荐

    js-leetcode题解之161-one-edit-distance.js

    javascript js_leetcode题解之161-one-edit-distance.js

    python-leetcode题解之161-One-Edit-Distance.py

    python python_leetcode题解之161_One_Edit_Distance.py

    _leetcode-python.pdf

    - Edit Distance: 给定两个单词word1和word2,计算将word1转换为word2所使用的最少操作数。 - Set Matrix Zeroes: 给定一个m×n的矩阵,如果一个元素为0,则将其所在行和列的所有元素都变为0。 - Search a 2D Matrix...

    LeetCode最全代码

    477 | [Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/) | [C++](./C++/total-hamming-distance.cpp) [Python](./Python/total-hamming-distance.py) | _O(n)_ | _O(1)_ | Medium ...

    leetcode316-algorithm-code-csharp:C#算法题汇总

    10. LeetCode第1081题:"One Edit Distance"(单编辑距离):判断两个字符串之间是否只需要一次编辑操作(插入、删除或替换)就可以互相转换。 11. LeetCode第1310题:"XOR Queries of a Subarray"(子数组异或查询...

    Leetcode book刷题必备

    14. One Edit Distance:判断两个字符串是否只差一个字符操作。 15. Read N Characters Given Read4:一次调用 read4() 可以读取 4 个字符,编写一个函数,使其能够读取 n 个字符。 16. Read N Characters Given ...

    uber leetcode

    #### 十、One Edit Distance - **知识点:**动态规划、字符串比较。 - **题目描述:**给定两个字符串word1和word2,返回使word1和word2相同所需的最小步数。每步可以插入一个字符、删除一个字符或者替换一个字符。 -...

    常见算法题答案及解析

    14. One Edit Distance:判断两个字符串是否相差一个字符,通常用来判断是否为编辑距离为一的字符串。 15. Read N Characters Given Read4:使用API读取文件中的N个字符,解决读取溢出问题。 16. Read N Characters ...

Global site tag (gtag.js) - Google Analytics