字符串常用算法：最长公共前缀、回文子串与数值运算

一、14. 最长公共前缀

题目链接：14. 最长公共前缀

解题思路

• 思路一：两两求公共前缀，记录在结果字符串中，继续与后续字符串比较。
• 思路二：以第一个字符串为基准，遍历其字符并与数组中其他字符串对应下标字符比较。若超出某字符串长度或字符不同则返回；若遍历完未找到差异，则第一个字符串即为结果。

解题代码

// 思路一：时间复杂度 O(m*n)，空间复杂度 O(1)
class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 两两比较
        String ret = strs[0];
        for (int i = 1; i < strs.length; i++) {
            ret = commonPrefix(ret, strs[i]);
        }
        return ret;
    }

    // 返回两个字符串的公共前缀
    private String commonPrefix(String s1, String s2) {
        int last = 0;
        while (last < s2.length() && last < s1.length() && s2.charAt(last) == s1.charAt(last)) {
            last++;
        }
        return s1.substring(0, last);
    }
}

// 思路二：时间复杂度 O(m*n)，空间复杂度 O(1)
class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 一起比较
        for (int i = 0; i < strs[0].length(); i++) {
            char ch = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || ch != strs[j].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

二、5. 最长回文子串

题目链接：5. 最长回文子串

解题思路

• 中心扩散法：从回文串的中心开始向两边扩展。如果两边字母相同则继续扩展，否则停止。
• 需分别考虑回文子串长度为奇数和偶数的情况。

解题代码

// 时间复杂度 O(n^2)，空间复杂度 O(1)
class Solution {
    public String longestPalindrome(String s) {
        String ret = "";
        for (int i = 0; i < s.length(); i++) {
            // 奇数长度
            int left = i;
            int right = i;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if (right - left - 1 > ret.length()) {
                ret = s.substring(left + 1, right);
            }

            // 偶数长度
            left = i;
            right = i + 1;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if (right - left - 1 > ret.length()) {
                ret = s.substring(left + 1, right);
            }
        }
        return ret;
    }
}

三、67. 二进制求和

题目链接：67. 二进制求和

题目解析

模拟竖式加法过程。

解题思路

• 模拟竖式加法，从后向前遍历两个字符串。
• 定义变量存储对应位相加的和，对 2 取余得到结果位，除以 2 得到进位。
• 当两个字符串都遍历结束且进位为 0 时，得到逆序后的结果字符串。
• 最后逆序返回即可。

解题代码

// 时间复杂度 O(n)，空间复杂度 O(1)
class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ret = new StringBuffer();
        int cruA = a.length() - 1;
        int cruB = b.length() - 1;
        int tmp = 0;
        while (cruA >= 0 || cruB >= 0 || tmp != 0) {
            if (cruA >= 0) tmp += a.charAt(cruA--) - '0';
            if (cruB >= 0) tmp += b.charAt(cruB--) - '0';
            ret.append((char) (tmp % 2 + '0'));
            tmp /= 2;
        }
        return ret.reverse().toString();
    }
}

四、43. 字符串相乘

题目链接：43. 字符串相乘

题目解析

将字符串视为数字，计算乘积并返回字符串形式。

解题思路

• 使用竖式运算规则，先不进位，在最后结果中统一处理进位。
• 竖式计算从末尾开始，先将两个字符串逆序。
• 每个位计算结果在结果数组中的下标为原来两个字符串下标之和。
• 进位时将每位数字除以 10 的结果记录到进位变量中。
• 处理前导零（如 152 * 0 = 000），注意极端情况全为 0 时保留一位。

解题代码

// 时间复杂度 O(n*m)，空间复杂度 O(n+m)
class Solution {
    public String multiply(String num1, String num2) {
        int[] arr = new int[num1.length() + num2.length() - 1];
        // 逆序
        char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();

        // 无进位相乘，相加
        for (int i = 0; i < n1.length; i++) {
            for (int j = 0; j < n2.length; j++) {
                arr[i + j] += (n1[i] - '0') * (n2[j] - '0');
            }
        }

        // 进位
        int tmp = 0;
        int cur = 0;
        StringBuffer ret = new StringBuffer();
        while (cur < arr.length || tmp > 0) {
            if (cur < arr.length) tmp += arr[cur++];
            ret.append((char) (tmp % 10 + '0'));
            tmp /= 10;
        }

        // 处理前导零
        while (ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
            ret.deleteCharAt(ret.length() - 1);
        }
        return ret.reverse().toString();
    }
}