本文共 2489 字，大约阅读时间需要 8 分钟。

01.05 一次编辑

首先，让我们看看怎么判断两个字符串只需要一次编辑操作或者没有编辑操作即可。具体想法如下：

思考过程： 两个字符串可能只需要一次编辑，或者根本不需要编辑。比如，如果两个字符串完全相同，就是不需要编辑的；如果只插入、删除或替换一个字符就能让它们相等，也就是只需要一次编辑。

实现思路： 我们可以用双指针的方法，一边从头向前遍历，另一边从尾向后遍历。一旦发现两个字符不一样，就分别统计从后面开始到不一样处的字符数。然后判断前面和后面剩下的字符数是否都小于等于1。总的情况，其实可以分为以下几种：

代码示例：

public class Solution {
    public static boolean oneEditAway(String first, String second) {
        if (first.equals(second)) {
            return true;
        }
        int len1 = first.length();
        int len2 = second.length();
        if (Math.abs(len1 - len2) > 1) {
            return false;
        }
        int i = 0;
        int j = len1 - 1;
        int k = len2 - 1;
        // 前进指针遍历前方
        while (i < len1 && i < len2 && first.charAt(i) == second.charAt(i)) {
            i++;
        }
        // 后退指针遍历后方
        while (j >= 0 && k >= 0 && first.charAt(j) == second.charAt(k)) {
            j--;
            k--;
        }
        // 判断是否只相差一个字符
        return (j >= i - 1 && k >= i - 1);
    }
}

也就是说，上面的算法比较简单直接地用两个指针分别从前往后和从后往前扫描，一旦发现不同就立即终止，然后再检查剩下的部分是否可以通过一次编辑操作来统一。

01.06 字符串压缩

接下来，我们来看看如何压缩字符串。简单地说，压缩的意思就是说，记录重复的字符。比如 aabbbc 可以被压缩成 a2b3c。如果压缩后的字符串长度不比原字符串短，那就返回原字符串。

思考过程： 需要一个方法来遍历字符串，记录每个字符连续出现的次数，然后把这个信息记录下来。比如，我们可以用双指针法，记录当前字符的起始位置和结束位置。一旦遇到不同的字符，就输出当前字符和出现的次数。

实现步骤：

代码示例：

public class StringUtil {
    public static String compressString(String S) {
        int count = 0;
        int n = S.length();
        if (n == 0) {
            return "";
        }
        StringBuilder result = new StringBuilder();
        char currentChar = S.charAt(0);
        count++;
        for (int i = 1; i < n; i++) {
            if (S.charAt(i) == currentChar) {
                count++;
            } else {
                result.append(currentChar);
                result.append(count);
                currentChar = S.charAt(i);
                count = 1;
            }
        }
        // 最后还要处理最后一组字符
        result.append(currentChar);
        result.append(count);
        // 如果压缩后的长度比原来长，则返回原字符串
        return result.length() < n ? result.toString() : S;
    }
}

上述代码的思路非常直观：

这种方法的时间复杂度是O(n)，所以非常高效。

转载地址：http://gzhtz.baihongyu.com/