算法专题：字符串

目录

1. 最长公共前缀

1.1 算法原理

1.2 算法代码

2. 最长回文子串

2.1 算法原理

2.2 算法代码

3. 二进制求和

3.1 算法原理

 3.2 算法代码

4. 字符串相乘

4.1 算法原理 

4.2 算法代码

1. 最长公共前缀

. - 力扣（LeetCode）

1.1 算法原理

有以下两种策略:

1. 两两进行比较
2. 统一进行比较

这里需要注意比较的结束条件:

1. 当对任一字符串访问出现越界时, 应进行返回
2. 当两个字符串相同位置上的元素不相同时, 应进行返回.

1.2 算法代码

class Solution {
    /**
     * 两两比较
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        String ret = strs[0];
        for(int i = 1; i < strs.length; i++) {
            ret = findSame(ret, strs[i]);
        }
        return ret;
    }
    public String findSame(String s1, String s2) {
        String ret = "";
        int i = 0;
        while(i < Math.min(s1.length(), s2.length()) && s1.charAt(i) == s2.charAt(i))
            i++;
        return s1.substring(0, i);
    }

    /**
     * 统一比较
     * @param strs
     * @return
     */
    public String longestCommonPrefix1(String[] strs) {
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < strs[0].length(); i++) {
            char ch = strs[0].charAt(i);
            for(String str : strs) {
                if(i >= str.length()) return ret.toString();
                if(str.charAt(i) != ch) return ret.toString();
            }
            ret.append(ch);
        }
        return ret.toString();
    }
}

2. 最长回文子串

. - 力扣（LeetCode）

2.1 算法原理

本题有动态规划和中心扩展算法两个解法, 动态规划的解法已经在动态规划的专题上展示了, 这里使用中心扩展算法:

1. 固定一个中心点
2. 从中心点开始, 向两边扩展(注意: 子串长度为奇数和偶数的情况都要考虑)

2.2 算法代码

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String ret = "";
        for(int i = 0; i < n; i++) {// 遍历中心位置
            int left = i, right = i;
            // 奇数子串
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            String str = s.substring(left + 1, right);
            ret = ret.length() >= str.length() ? ret : str;
            // 偶数子串
            left = i; right = i + 1;
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            str = s.substring(left + 1, right);
            ret = ret.length() >= str.length() ? ret : str;
        }
        return ret;
    }
}

3. 二进制求和

. - 力扣（LeetCode）

3.1 算法原理

本题本质上是一到模拟题, 模拟高精度加法. 高精度, 就是指 数非常的大, 数据的长度非常的长.

1. 关键点在于遍历两个字符串
2. 使用 tmp 记录两个字符串相同的位置相加后的值
3. tmp % 2 => 结果值(二进制)
4. tmp / 2 => 相加所得的进位

 3.2 算法代码

class Solution {
    public String addBinary(String a, String b) {
        // 模拟高精度加法
        int cur1 = a.length() - 1;
        int cur2 = b.length() - 1;
        int tmp = 0;
        StringBuilder sb = new StringBuilder();
        while(cur1 >= 0 || cur2 >= 0 || tmp != 0) {
            if(cur1 >= 0) tmp += a.charAt(cur1--) - '0';
            if(cur2 >= 0) tmp += b.charAt(cur2--) - '0';
            sb.append(tmp % 2);
            tmp /= 2;
        }
        return sb.reverse().toString();
    }
}

4. 字符串相乘

. - 力扣（LeetCode）

4.1 算法原理 

解法: 无进位相乘再相加, 最后处理进位

1. 逆序字符串
2. 无进位相乘再相加(将得到的结果使用数组存起来, 放到 i+j 位置处)
3. 处理进位
4. 处理前导零

4.2 算法代码

class Solution {
    public String multiply(String num1, String num2) {
        // 解法: 无进位相乘再相加, 最后处理进位

        // 预处理
        int m = num1.length(), n = num2.length();
        int[] arr = new int[m + n - 1];
        StringBuilder s1 = new StringBuilder(num1);
        StringBuilder s2 = new StringBuilder(num2);
        s1.reverse();
        s2.reverse();
        // 无进位相乘再相加
        for(int i = 0; i < m; i++) 
            for(int j = 0; j < n; j++) 
                arr[i + j] += (s1.charAt(i) - '0') * (s2.charAt(j) - '0');
        StringBuilder ret = new StringBuilder();
        int t = 0;
        int i = 0;
        // 处理进位
        while(i < arr.length || t != 0) {
            if(i < arr.length) t += arr[i++];
            ret.append(t % 10);
            t /= 10;
        }
        // 处理前导零
        ret.reverse();
        while(ret.charAt(0) == '0' && ret.length() > 1) ret.deleteCharAt(0);
        return ret.toString();
    }
}

END