【算法】【优选算法】字符串
目录
一、14.最⻓公共前缀
题目链接：14.最⻓公共前缀
题目描述：
解题思路：
- 思路一：
- 我们直接两两求一下公共前缀，记录在ret字符串中，然后ret与后续继续求公共前缀，最后的ret就是结果
- 求公共前缀，我们就求一下在字符串中的公共前缀的最后一个字符 的下一个下标即可。
- 思路二：
- 我们就将第一个字符串作为基准，遍历字符串，每个字符再与字符串数组中剩下的字符串，对应下标的字符比较即可。
- 当超出某个字符串长度或者字符不同了，就可以返回了。
- 最后第一个字符串都遍历完了，还没找到，那么第一个字符串就是结果。
解题代码：
思路一： //时间复杂度：O(m*n)//空间复杂度：O(1)classSolution{publicStringlongestCommonPrefix(String[] strs){//两两比较String ret = strs[0];for(int i =1; i < strs.length; i++){ ret =commonPrefix(ret, strs[i]);}return ret;}//返回两个字符串的公共前缀publicStringcommonPrefix(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)classSolution{publicStringlongestCommonPrefix(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)classSolution{publicStringlongestPalindrome(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)classSolution{publicStringaddBinary(String a,String b){StringBuffer ret =newStringBuffer();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.字符串相乘
题目描述：
题目解析：
- 就相当于每个字符串就是一个数，让我们求乘积，乘积也放在字符串中。
解题思路：
- 还是使用小学的竖式运算规则，
- 但是有所不同的是，我们先不进位（就是如果3*8=24，先不进2），在最后的结果中来进位。
- 我们竖式计算过程是从末尾先开始的，所以我们先将两个字符串逆序。
- 通过竖式计算过程，每个位计算结果在结果中的下标就是原来两个字符串的下标之和
- 在进位的时候，我们只需要将每位数字 ，除以10的结果记录在一个变量中，然后这个变量就是进位的数。
- 现在得到的结果还可能会有前导零：前导零就是指152 * 0 = 000 这就有两个前导零。
- 由于现在的结果是逆序的，所以从最后开始检验，有就删，注意极端情况全为0的时候，还要保留一位。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(n)classSolution{publicStringmultiply(String num1,String num2){int[] arr =newint[num1.length()+ num2.length()-1];//逆序char[] n1 =newStringBuffer(num1).reverse().toString().toCharArray();char[] n2 =newStringBuffer(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 =newStringBuffer();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();}}
