字符串专题题目一 leetcode14.最长公共前缀题⽬描述编写⼀个函数来查找字符串数组中的最⻓公共前缀。如果不存在公共前缀返回空字符串 。⽰例 1输⼊strs [flower,flow,flight]输出fl⽰例 2输⼊strs [dog,racecar,car]输出解释输⼊不存在公共前缀。提⽰1 strs.length 2000 strs[i].length 200strs[i] 仅由⼩写英⽂字⺟组成解法思路一两两比较以字符数组第一个字符串tmp为基准最初的公共字符串长度为第一个字符串的长度retLen取retLen与所比较的字符串的长度较小的作为遍历次数比较前将retLen置为0然后与strs中的后一个字符串进行比较每有一个字符相同则retLen遍历完成后得到新的公共前缀长度不断重复这个过程直至所有的字符串比较完成结果返回tmp的长度为retLen的字串即为最长的公共前缀。时间复杂度分析假设共有n个字符串每个字符串的长度为m整个过程相当于将每个字符串都要遍历一次所以时间复杂度为On * m)。核心代码实现public String longestCommonPrefix(String[] strs) { if(strs.length 1 || strs[0].isEmpty()) return strs[0]; String tmp strs[0]; int retLen tmp.length(); for(int i 1;i strs.length;i){ int len Math.min(retLen,strs[i].length()); retLen 0; for(int j 0;j len;j){ if(tmp.charAt(j) ! strs[i].charAt(j)){ break; } retLen; } } return tmp.substring(0,retLen); }思路二所有字符串统一进行比较用一个for循环表示遍历到第i个字符用第二层循环以strs[0]的第i个字符为基准然后将数组中所有字符串的该位置字符进行比较如果此时字符串长度等于i越界了或者字符不匹配则说明不符合条件则前面已经遍历过的字符串就是最长公共前缀此时直接返回即可。时间复杂度分析假设共有n个字符串每个字符串的长度为m每次循环遍历n个字符串的一个字符重复m次所以时间复杂度为Om * n。核心代码实现public String longestCommonPrefix(String[] strs) { if(strs.length 1 || strs[0].isEmpty()) return strs[0]; for(int i 0;i strs[0].length();i){ //记录用于比较的基准字符 char tmp strs[0].charAt(i); for(int j 1;j strs.length;j){ if(strs[j].length() i || strs[j].charAt(i) ! tmp){ //如果找到不符合的那长度就与当前i下标相等直接返回 return strs[0].substring(0,i); } } } //能走完循环说明整个strs[0]都属于公共前缀 return strs[0]; }题目二leetcode5.最长回文子串题⽬描述给你⼀个字符串 s找到 s 中最⻓的回⽂⼦串。如果字符串的反序与原始字符串相同则该字符串称为回⽂字符串。⽰例 1输⼊s babad输出bab解释aba 同样是符合题意的答案。⽰例 2输⼊s cbbd输出bb提⽰1 s.length 1000s 仅由数字和英⽂字⺟组成解法思路一暴力查找遍历数组定一个字符再次嵌套遍历字符没得到一个字符串就判断一次是否是回文字符如果是回文字符串且长度大于已有结果则更新结果重复这个过程直至所有可能全部判断完毕。时间复杂度分析遍历的过程O(n^2),判断回文的过程O(n),所以总的时间复杂度为O(n^3)。public class Solution { public String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } int start 0; int end 0; for (int i 0; i s.length(); i) { int len1 expandAroundCenter(s, i, i); int len2 expandAroundCenter(s, i, i 1); int len Math.max(len1, len2); if (len end - start) { start i - (len - 1) / 2; end i len / 2; } } return s.substring(start, end 1); } private int expandAroundCenter(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } return right - left - 1; } }思路二中心扩散规则遍历数组与思路一不同的是此时我们将遍历到的字符作为中心字符定义两个指针left和right向两边查找如果left和right都没有越界并且两个指针所指向的字符相等则继续查找否则跳出循环判断此时的长度是否大于已有结果是则更新然后遍历下一个字符重复这个过程直至遍历完所有字符。注意点1.由于回文字符有奇数和偶数两种所以我们可以先判断奇数情况left和right分别指向当前字符的前一个和后一个字符如果不符合条件就判断偶数情况都不符合则不是回文字符串。2.这里因为取的是right和left之间的数所以长度计算为right - left - 1。时间复杂度分析遍历所需时间与思路一相同但是在遍历的过程中已经同时判断了是否是回文字符串不需要再单独进行这一步所以时间复杂度为O(n^2)。核心代码实现public String longestPalindrome(String s) { int len 0,lp 0,rp 0; for(int i 0;i s.length();i){ //奇数情况 int left i - 1,right i 1; //left和right移动的条件 while(left 0 right s.length() s.charAt(left) s.charAt(right)){ left--; right; } //此时的left和right都在不合法的位置越界或者不符合条件 if(right - left - 1 len){ lp left 1; rp right - 1; len right - left - 1; } //偶数情况 left i; right i 1; while(left 0 right s.length() s.charAt(left) s.charAt(right)){ left--; right; } if(right - left - 1 len){ lp left 1; rp right -1; len right - left - 1; } } return s.substring(lp,rp 1); }题目三leetcode67.二进制求和题⽬描述给你两个⼆进制字符串 a 和 b 以⼆进制字符串的形式返回它们的和。⽰例 1输⼊:a 11, b 1输出100⽰例 2输⼊a 1010, b 1011输出10101思路这道题本质上是用模拟算法模拟竖式计算竖式计算中我们都是从末尾开始计算所以我们首先将两个字符串逆序(逆序不需要真的把字符串反转只需要让指针从后往前遍历即可然后模拟竖式计算的过程每一位先相加得到结果追加到结果中然后进位并进行下一步的计算重复上述过程直至完成计算。这里需要把计算得到的每一位不断添加到字符串中所以用到了StringBuilder来进行操作。用到的Java方法1.字符转整数用 “ 字符 - 0 ”。2.字符串的访问逆序或者正序都不需要转数组直接用str.charAt();3.StringBuilder的reverse方法可以直接逆序字符串。代码的简化由于字符串长度不一样用一个指针无法同时遍历两个字符串可以要用两个指针分开遍历这样就可以把两个条件放进一个循环只需要进入循环时判定两个指针是否越界本来长的字符串多出来的部分需要再进行一次循环的部分可以去掉同时最后的进位也可以直接在这个循环里进行。核心代码实现class Solution { public String addBinary(String a, String b) { StringBuilder sb new StringBuilder(); int cur1 a.length() - 1,cur2 b.length() - 1,tmp 0; //把三个循环合成一个条件写到一起 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; } sb.reverse(); return sb.toString(); } }题目四leetcode43.字符串相乘题⽬描述给定两个以字符串形式表⽰的⾮负整数 num1 和 num2返回 num1 和 num2 的乘积它们的乘积也表⽰为字符串形式。注意不能使⽤任何内置的 BigInteger 库或直接将输⼊转换为整数。⽰例 1:输⼊: num1 2, num2 3输出: 6⽰例 2:输⼊: num1 123, num2 456输出: 56088解法思路一直接模拟和二进制加法一样首先把字符串逆序模拟竖式相乘个位相乘完取余得到结果先存到ret数组对应的位置里用一个变量存储进位继续与下一位相乘相乘完之后加上进位重复直至个位与另一个数的每一位都进行了相乘然后下一位数十位、百位再重复上述过程直至把所有完成计算。这里可以用字符串或者数组进行存储。注意点如果用的是字符串模拟上一题二进制相加1.当不是个位相乘的时候得到的结果后面其实是需要加零的先把得到的字符串逆序然后在字符串末尾添加零由于先把字符串逆序零的个数与当前已经遍历的次数相同用一个变量记录一下他的位数比如十位逆序遍历时是第二位已经遍历了一位则在结果后面加1个零。2.如果是零相乘得到的是零但是得到的结果可能是多个零所以需要处理前导零。处理前导零法一先变成正序在指针length() 1的情况下,如果结果字符串的第一位是零则说明是前导零直接删除。法二逆序情况下s.length() 1的情况下如果最后一位为零则说明是前导零,直接删除。核心代码实现这个代码过于复杂不建议使用计算乘法是多维运算不像加法可以一直在同一维一直进位即可所以最好采用数组class Solution { public String multiply(String num1, String num2) { int cur num1.length() - 1; StringBuilder ret new StringBuilder(); int index 0; for(int i num2.length() - 1;i 0;i--){ StringBuilder sb new StringBuilder(); int tmp 0; cur num1.length() - 1; while(cur 0 || tmp ! 0){ if(cur 0) tmp (num1.charAt(cur--) - 0) *(num2.charAt(i) - 0); sb.append(tmp % 10); tmp / 10; } sb.reverse(); //补零 for(int j 0;j index;j){ sb.append(0); } //把结果相加 int cur1 ret.length() - 1,cur2 sb.length() - 1,carry 0; StringBuilder tmpsb new StringBuilder(); while(cur1 0 || cur2 0 || carry ! 0){ if(cur1 0) carry ret.charAt(cur1--) - 0; if(cur2 0) carry sb.charAt(cur2--) - 0; tmpsb.append(carry % 10); carry carry / 10; } index; ret tmpsb.reverse(); } //删除前导零 if(ret.charAt(0) 0) return 0; return ret.toString(); } }如果用的是数组1..num1的第i位和num2的第j位相乘结果直接存储到ret[i j]位num1要偏移i位nums2要偏移j位。2.如果num1有n位数num2有m位数存储结果的数组大小为[m n],最后一位数与最后一位相乘的时候放到[n - 1 m - 1]位如果有进位则放在[n - 1 m]位也就是数组长度至少为[m n]。3.前置零问题。4.每次相加是原来已经存在数组该位置的数叠加上取模得到的数此时同样还有可能超过十需要再进行处理。核心代码public String multiply(String num1, String num2) { //逆序字符串 num1 new StringBuilder(num1).reverse().toString(); num2 new StringBuilder(num2).reverse().toString(); int len1 num1.length(); int len2 num2.length(); //存储计算结果 int[] ret new int[len1 len2]; //移动num2 for(int i 0;i len2;i){ //移动num1,计算并进位 int tmp 0,cur 0; while(cur len1 || tmp ! 0){ if(cur len1) tmp (num2.charAt(i) - 0) * (num1.charAt(cur) - 0); ret[i cur] tmp % 10; tmp / 10; if(ret[i cur] 0){ tmp (ret[i cur] / 10); ret[i cur] % 10; } cur; } } StringBuilder rets new StringBuilder(); for(int i :ret){ rets.append(i); } while(rets.length() 1 rets.charAt(rets.length() - 1) 0) rets.deleteCharAt(rets.length() - 1); return rets.reverse().toString(); }思路二无进位相加思路一的麻烦点在于我们需要相加进位每次不仅乘完需要进位每次结果相加的时候也需要进位所以优化的方法就是采用无进位相加。每次相乘得到的结果无需进位此时我们需要用数组把这个数存储下来依旧先逆序存储当十位或百位这样的位数进行乘法时也不需要再补零直接偏移存储就行了当所有乘法完成之后再对存储结果的数组进行进位操作最后逆序就能得到结果。注意问题1.num1的第i位和num2的第j位相乘结果直接存储到ret[i j]位num1要偏移i位nums2要偏移j位。2.如果num1有n位数num2有m位数ret数组只需开[m n -1]位因为最后一位存结果的位是m - 1 n - 1 m n - 2此时最多再加一位进位所以是m n - 1位3.前置零问题。核心代码class Solution { public String multiply(String num1, String num2) { int m num1.length(),n num2.length(); int[] ret new int[m n - 1]; String s1 new StringBuilder(num1).reverse().toString(); String s2 new StringBuilder(num2).reverse().toString(); //无进位相乘 for(int i 0;i n;i){ for(int j 0;j m;j){ ret[i j] (s2.charAt(i) - 0) * (s1.charAt(j) - 0); } } //处理进位 int tmp 0,cur 0; StringBuilder sb new StringBuilder(); while(cur ret.length || tmp ! 0 ){ if(cur ret.length) tmp ret[cur]; sb.append(tmp % 10); tmp tmp / 10; } //在逆序字符串中处理前置零(删末尾的零) while(sb.length() 1 sb.charAt(sb.length() - 1) 0) sb.deleteCharAt(sb.length() - 1); return sb.reverse().toString(); } }总结字符串处理常结合模拟算法通过遍历、截取、替换等操作实现逻辑。字符串的不可变性部分语言和索引特性使得操作需借助临时存储如数组或指针双指针、滑动窗口优化效率。