算法——字符串

在这里插入图片描述

T04BF
👋热门专栏: 算法|JAVA|MySQL|C语言
🫵 小比特大梦想

此篇文章与大家分享字符串相关算法
如果有不足的或者错误的请您指出!

1.最长公共前缀

题目:最长公共前缀

1.1解析

有两种比较方式,一种是两个两个比较,比较得出的最长公共前缀再和另一个比较;另一种就是统一比较,每次都比较所有字符串相同下标的字符,直到遇到不相同的字符或者某一串字符串已经遍历完了
本文采用的是第二种方法

1.2题解

class Solution {
    public static 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];//说明此时第一串字符就是最长公共前缀
    }
}

2.最长回文子串

题目:最长回文子串

2.1解析

我们最容易想到的就是暴力解法,即对每一个子串都进行判断,但是时间复杂度来到了O(n^3)
但是实际上我们可以通过"回文字符串"的特点来进行判断
在这里插入图片描述
如图所示,我们用i来遍历字符串,同时定义left和right变量,left往左走,right变量往后走,每次都判断left下标的字符和right下标的字符是否相等,如果不相等或者left/right超过边界条件,那么此时left 和 right 就是以i下标字符为中心的最长回文字符串
但是实际上这只是考虑奇数个数字符的字符串,因此我们找完奇数情况后还要找偶数情况
在这里插入图片描述
如图所示,我们可以让left = i,right = i+1,按照上面的方法去寻找即可

此时时间复杂度降为O(n^2)

2.2题解

class Solution {
    public String longestPalindrome(String s) {
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            int l = i;
            int r = i;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                l--;
                r++;
            }
            if(right - left < r - l){
                right = r;
                left = l;
            }
            l = i;
            r = i+1;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                l--;
                r++;
            }
            if(right - left < r - l){
                right = r;
                left = l;
            }
        }
        return s.substring(left+1,right);
    }
}

3.二级制求和

题目:二级制求和

3.1解析

实际上无论是二进制、十进制还是其他进制相加，我们只要模拟出来我们常用的两数相加的过程就好了
在这里插入图片描述
对于二进制就是满2就进位，我们只需要在下一次计算的时候将上一次的进位加上就好了
思路比较简单，我们直接通过代码体现

3.2题解

class Solution {
    public String addBinary(String a, String b) {
        int len1 = a.length();
        int len2 = b.length();
        int cur1 = len1-1;
        int cur2 = len2-1;
        int tmp = 0;
        StringBuilder ret = new StringBuilder();
        while(cur1 >= 0 || cur2 >= 0 || tmp != 0){
            if(cur1 >= 0){
                tmp += a.charAt(cur1) - '0';
                cur1--;
            }
            if(cur2 >= 0){
                tmp += b.charAt(cur2) - '0';
                cur2--;
            }
            ret.append(tmp % 2);
            tmp /= 2;
        }
        return ret.reverse().toString();
    }
}

4.字符串相乘

题目:字符串相乘

4.1解析

我们还是模拟我们现实中来两数相乘的计算方式
在这里插入图片描述
思路比较简单,但是这种解法细节还是很多的
(1)高位相乘的时候要补上0
即我们最后进行相加的时候,不是738和615相加,而是738和6150相加
(2)处理前导0
假设题目给我们是

但是我们只要的是一个0即可,我们就要处理前面的0
(3)字符串的顺序
对于这种大数的四则运算题目,我们最好都是将字符串先逆置过来,即将个位数放在下标为0的位置,这样我们每次进行计算的时候就直接从下标为1的位置开始计算,最后再将答案逆置即可

而第二种解法实际上是对第一种解法的优化
我们的处理策略是先不考虑进位,直接"无进位相乘"后,得到的结果再考虑进位
在这里插入图片描述
此时得到的答案和我们上面是完全一样的
但是这种方法给我们带来的很大的便利
首先我们每次相乘得到数应该存放到以一个数组里,即上面的6 12 18这些数字,假设我们的数组是tmp
而tmp数组的长度最大也就是m+n-1
在这里插入图片描述
那么我们会发现,实际上当下标为i的字符和下标为j的字符相乘后,得到的数字是放在 tmp 数组的 [i+j]下标位置的
这样一来我们就不再需要进行什么高位补0的操作了
同时,我们最后将每次相乘得到的数字进行相加的操作,无非就是tmp数组每次累加即可

4.2题解

class Solution {
    public String multiply(String num1, String num2) {
        int n1 = num1.length();
        int n2 = num2.length();
        int[] tmp = new int[n1+n2-1];
        num1 = new StringBuilder(num1).reverse().toString();//原字符串逆置
        num2 = new StringBuilder(num2).reverse().toString();
        for(int i = 0; i < n1; i++){
            for(int j = 0; j < n2; j++){
                tmp[i+j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }
        int k = 0;
        int t = 0;
        StringBuilder ret = new StringBuilder();
        //进位
        while(k < tmp.length || t != 0){
            if(k < tmp.length){
                t += tmp[k++];
            }
            ret.append(t % 10);
            t /= 10;
        }
        
        ret.reverse();
        //处理前导0
        k = 0;
        while(k < ret.length()-1 && ret.charAt(k) == '0'){
            k++;
        }
        return ret.substring(k);
    }
}