2025年高频string面试试题及答案

2025年高频string面试试题及答案1.反转字符串中的单词顺序（含多空格处理）输入字符串s可能包含前导、尾随空格及多个空格分隔单词，要求输出反转单词顺序后的字符串，且单词间仅保留一个空格。思路：首先去除首尾空格，然后按空格分割成单词数组（需处理连续空格），反转数组后重新拼接。关键在于分割时过滤空字符串，并处理边界情况。Java实现：```javapublicStringreverseWords(Strings){//去除首尾空格，分割成单词数组（过滤空字符串）String[]words=s.trim().split("+");Collections.reverse(Arrays.asList(words));returnString.join("",words);}```复杂度：时间O(n)（trim、split、反转均线性时间），空间O(n)（存储单词数组）。扩展：若要求原地反转（假设字符数组输入），需先整体反转，再逐个单词反转。例如输入char[]s，先反转整个数组，再遍历找到每个单词的首尾位置反转。2.最长无重复字符的子串（滑动窗口优化）给定字符串s，找出最长不含重复字符的子串长度。思路：滑动窗口[left,right]表示当前无重复子串，用哈希表记录字符最后出现的位置。右指针右移时，若字符已存在且位置≥left，则更新left为max(left,字符位置+1)，同时更新最大长度。Python实现：```pythondeflengthOfLongestSubstring(s:str)->int:char_map={}max_len=left=0forright,charinenumerate(s):ifcharinchar_mapandchar_map[char]>=left:left=char_map[char]+1char_map[char]=rightmax_len=max(max_len,rightleft+1)returnmax_len```复杂度：时间O(n)（每个字符访问一次），空间O(min(m,n))（m为字符集大小，如ASCII则O(128)）。扩展：若字符集为Unicode，改用哈希表；若要求返回子串本身，需记录left和max_left的位置。3.有效的括号字符串（多状态校验）给定字符串s含'('、')'、''，''可视为'('、')'或空，判断是否有效。思路：维护两个变量low和high，分别表示当前可能的未闭合左括号数的最小和最大值。遍历字符：遇'('：low和high均+1；遇')'：low和high均-1（low≥0）；遇''：low-1（视为')'），high+1（视为'('）。若high<0则提前返回false，最终low≤0≤high。Java实现：```javapublicbooleancheckValidString(Strings){intlow=0,high=0;for(charc:s.toCharArray()){if(c=='('){low++;high++;}elseif(c==')'){if(low>0)low--;high--;}else{//''if(low>0)low--;high++;}if(high<0)returnfalse;//无法抵消右括号}returnlow==0;}```复杂度：时间O(n)，空间O(1)。关键点：通过上下界约束确保所有可能情况被覆盖，避免递归或动态规划的高空间消耗。4.字符串转换整数（处理边界条件）实现atoi函数，将字符串转为32位有符号整数（超出范围返回±2^31）。步骤：1.跳过前导空格；2.确定符号（+/-，默认+）；3.遍历数字字符，累加结果并检查溢出：若res>Integer.MAX_VALUE/10，或res==MAX/10且当前数字>7（正数）或>8（负数），则溢出。Java实现：```javapublicintmyAtoi(Strings){inti=0,n=s.length();//跳过空格while(i<n&&s.charAt(i)=='')i++;if(i==n)return0;//符号位intsign=1;if(s.charAt(i)=='+'||s.charAt(i)=='-'){sign=s.charAt(i)=='-'?-1:1;i++;}//转换数字intres=0;while(i<n&&Character.isDigit(s.charAt(i))){intdigit=s.charAt(i)'0';//检查溢出：res10+digit>Integer.MAX_VALUEif(res>Integer.MAX_VALUE/10||(res==Integer.MAX_VALUE/10&&digit>Integer.MAX_VALUE%10)){returnsign==1?Integer.MAX_VALUE:Integer.MIN_VALUE;}res=res10+digit;i++;}returnsignres;}```关键边界：INT_MAX=2^31-1=2147483647，INT_MIN=-2^31=-2147483648，因此当符号为负时，若digit>8（即2147483648的末位）则溢出。5.最长回文子串（Manacher算法）给定字符串s，找出最长回文子串。Manacher算法通过预处理（插入''）统一奇偶长度回文，利用回文对称性优化中心扩展。步骤：1.预处理字符串t，如"babad"→"babad"；2.维护数组p记录每个位置的回文半径，以及中心c和右边界r；3.遍历i，若i<r，利用对称点i'=2c-i的p[i']值初始化p[i]，否则初始化为1；4.扩展中心i，更新p[i]和c、r；5.遍历p数组找到最大半径，计算原字符串中的起始位置。Python实现（关键部分）：```pythondeflongestPalindrome(s:str)->str:ifnots:return""t=''+''.join(s)+''预处理n=len(t)p=[0]nc=r=max_len=res_c=0foriinrange(n):利用对称性初始化p[i]ifi<r:mirror=2cip[i]=min(ri,p[mirror])中心扩展a,b=i+p[i]+1,ip[i]1whilea<nandb>=0andt[a]==t[b]:p[i]+=1a+=1b-=1更新c和rifi+p[i]>r:c=ir=i+p[i]记录最大回文中心和半径ifp[i]>max_len:max_len=p[i]res_c=i转换回原字符串位置start=(res_cmax_len)//2returns[start:start+max_len]```复杂度：时间O(n)（每个字符最多扩展一次），空间O(n)（存储p数组）。优势：相比中心扩展法O(n²)，Manacher通过对称性将时间降至线性，适合处理长字符串。6.实现strStr()（KMP算法改进）给定haystack和needle，返回needle首次出现的索引（无则-1）。KMP核心是构建部分匹配表（前缀函数），记录模式串的最长相等前缀后缀长度，避免主串指针回退。Java实现（构建前缀数组+匹配）：```javapublicintstrStr(Stringhaystack,Stringneedle){if(needle.length()==0)return0;intn=haystack.length(),m=needle.length();int[]lps=computeLPS(needle);//最长前缀后缀数组inti=0,j=0;//i主串指针，j模式串指针while(i<n){if(haystack.charAt(i)==needle.charAt(j)){i++;j++;if(j==m)returnij;//匹配完成}else{if(j!=0)j=lps[j-1];//回退到前缀位置elsei++;//j=0时主串指针前进}}return-1;}privateint[]computeLPS(Strings){int[]lps=newint[s.length()];intlen=0,i=1;while(i<s.length()){if(s.charAt(i)==s.charAt(len)){len++;lps[i]=len;i++;}else{if(len!=0)len=lps[len-1];//回退else{lps[i]=0;i++;}}}returnlps;}```复杂度：时间O(n+m)（预处理O(m)，匹配O(n)），空间O(m)（存储LPS数组）。扩展：若模式串含大量重复字符（如"AAAAAB"），LPS数组能有效减少回退次数。7.字符串的排列（滑动窗口+计数）给定s1和s2，判断s2是否包含s1的排列（即s1的某个排列是s2的子串）。思路：滑动窗口保持长度为len(s1)，用数组count记录字符频率差。当窗口移动时，更新count，若全为0则返回true。Java实现：```javapublicbooleancheckInclusion(Strings1,Strings2){intn=s1.length(),m=s2.length();if(n>m)returnfalse;int[]count=newint[26];//初始化count：s1字符+1，s2前n字符-1for(inti=0;i<n;i++){count[s1.charAt(i)-'a']++;count[s2.charAt(i)-'a']--;}if(allZero(count))returntrue;//滑动窗口：每次移动右指针加入新字符，左指针移除旧字符for(inti=n;i<m;i++){count[s2.charAt(i)-'a']--;//右指针字符-1count[s2.charAt(i-n)-'a']++;//左指针字符+1（移出窗口）if(allZero(count))returntrue;}returnfalse;}privatebooleanallZero(int[]arr){for(intnum:arr){if(num!=0)returnfalse;}returntrue;}```复杂度：时间O(n+m)（n为s1长度，m为s2长度），空间O(1)（固定大小数组）。关键点：用频率差代替直接比较排列，避免了提供所有排列的高时间复杂度（O(n!)）。8.括号提供（回溯法优化）数字n代表提供n对括号，输出所有有效组合。优化思路：回溯时跟踪左右括号数量，仅当左括号<n时添加左括号，右括号<左括号时添加右括号，避免无效路径。Python实现：```pythondefgenerateParenthesis(n:int)->List[str]:res=[]defbacktrack(s,left,right):iflen(s)==2n:res.append(''.join(s))returnifleft<n:s.append('(')backtrack(s,left+1,right)s.pop()ifright<left:s.append(')')backtrack(s,left,right+1)s.pop()backtrack([],0,0)returnres```复杂度：时间O(4^n/√n)（Catalan数复杂度），空间O(n)（递归栈深度）。扩展：动态规划解法，dp[i]表示i对括号的有效组合，dp[i]='('+dp[j]+')'+dp[i-j-1]（j从0到i-1）。9.编辑距离（动态规划空间优化）给定两个字符串word1和word2，计算将word1转换成word2所需的最少操作数（插入、删除、替换）。动态规划状态定义：dp[i][j]表示word1前i字符转成word2前j字符的最小操作数。状态转移：若word1[i-1]==word2[j-1]，dp[i][j]=dp[i-1][j-1]；否则，dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1（删除、插入、替换）。空间优化：用一维数组prev和curr代替二维数组。Java实现（空间优化版）：```javapublicintminDistance(Stringword1,Stringword2){intm=word1.length(),n=word2.length();int[]prev=newint[n+1];//上一行dp值//初始化：word1为空时，插入n次for(intj=0;j<=n;j++)prev[j]=j;for(inti=1;i<=m;i++){int[]curr=newint[n+1];curr[0]=i;//word2为空时，删除i次for(intj=1;j<=n;j++){if(word1.charAt(i-1)==word2.charAt(j-1)){curr[j]=prev[j-1];}else{curr[j]=Math.min(Math.min(prev[j],curr[j-1]),prev[j-1])+1;}}prev=curr;}returnprev[n];}```复杂度：时间O(mn)，空间O(n)（优化后）。关键点：空间优化通过滚动数组减少内存消耗，适合处理大字符串。10.重复的子字符串（KMP失败函数应用）给定字符串s，判断是否由重复子串构成（如"abab"→"ab"重复2次）。思路：若s由重复子串t构成，则s=tk（k≥2），其长度n必为t长度的倍数。利用KMP的LPS数组（最长前缀后缀长度），若n%(nlps[n-1])==0，则存在重复子串。Java实现：```javapublicbooleanrepeatedSubstringPattern(Strings){intn=s.length();int[]lps=computeLPS(s);intlen=lps[n-1];//最长前缀后缀长度//若nlen是n的因数，则存在重复子串returnlen>0&&n%(nlen)==0;}privateint[]computeLPS(Strings){int[]lps=newint[s.length()];intlen=0,i=1;while(i<s.length()){if(s.charAt(i)==s.charAt(len)){len++;lps[i]=len;i++;}else{if(len!=0)len=lps[len-1];else{lps[i]=0;i++;}}}returnlps;}```原理：若存在重复子串t，则最长公共前后缀长度为nlen(t)，因此nlen(t)必须是n的因数。例如"ababab"的LPS最后一位是4（前缀"abab"和后缀"abab"），n=6，nlen=2，6%2=0，符合条件。11.有效回文串（考虑大小写和非字母数字）给定字符串s，判断是否为回文（忽略大小写，仅考虑字母数字）。思路：双指针法，左指针从左到右找有效字符，右指针从右到左找有效字符，比较是否相等（转换为小写）。Java实现：```javapublicbooleanisPalindrome(Strings){intleft=0,right=s.length()1;while(left<right){//跳过非字母数字while(left<right&&!Character.isLetterOrDigit(s.charAt(left)))left++;while(left<right&&!Character.isLetterOrDigit(s.charAt(right)))right--;//比较字符（转小写）if(Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right))){returnfalse;}left++;right--;}returntrue;}```复杂度：时间O(n)，空间O(1)。扩展：若允许删除一个字符判断是否回文（如"abca"），需增加辅助函数判断[left+1,right]或[left,right-1]是否为回文。12.字符串相乘（大数相乘处理）给定两个非负整数字符串num1和num2，返回乘积的字符串形式（不使用大数库或直接转整数）。思路：结果长度最多为m+n（m、n为两数长度），用数组res记录每一位的乘积和。num1[i]num2[j]的结果位于res[i+j]和res[i+j+1]。Java实现：```javapublicStringmultiply(Stringnum1,Stringnum2){if(num1.equals("0")||num2.equals("0"))return"0";intm=num1.length(),n=num2.length();int[]res=newint[m+n];for(inti=m-1;i>=0;i--){inta=num1.charAt(i)'0';for(intj=n-1;j>=0;j--){intb=num2.charAt(j)'0';intsum=ab+res[i+j+1];res[i+j+1]=sum%10;res[i+j]+=sum/10;}}//转换为字符串（跳过前导0）StringBuildersb=newStringBuilder();for(intnum:res){if(!(sb.length()==0&&num==0)){//避免全0时留空sb.append(num);}}returnsb.length()==0?"0":sb.toString();}```关键点：用数组存储每一位的中间结果，避免溢出；处理前导0时需判断是否全部为0。13.分割回文串（回溯+记忆化）给定字符串s，返回所有可能的回文子串分割方案（每个子串都是回文）。优化思路：回溯时，用记忆化数组记录s[i..j]是否为回文，避免重复计算。Python实现（记忆化+回溯）：```pythondefpartition(s:str)->List[List[str]]:n=len(s)memo=[[-1]nfor_inrange(n)]-1未计算，0非回文，1是回文res=[]defisPalindrome(i,j):ifi>=j:returnTrueifmemo[i][j]!=-1:returnmemo[i][j]==1ifs[i]==s[j]andisPalindrome(i+1,j-1):memo[i][j]=1else:memo[i][j]=0returnmemo[i][j]==1defbacktrack(start,path):ifstart==n:res.append(path.copy())returnforendinrange(start,n):ifisPalindrome(start,end):path.append(s[start:end+1])backtrack(end+1,path)path.pop()backtrack(0,[])returnres```复杂度：时间O(n2^n)（最多有2^n-1种分割方式，每次检查回文O(n)），记忆化后检查回文O(1)，总时间O(n2^n)。扩展：若要求最少分割次数，可用动态规划，dp[i]表示前i字符的最少分割数，dp[i]=min(dp[j]+1)（j<i且s[j..i-1]是回文）。14.验证IP地址（正则与逐段校验）给定字符串queryIP，判断是IPv4、IPv6还是无效。IPv4规则：4段，0-255，无前导零（除非是0）。IPv6规则：8段，每段1-4个十六进制数（0-9，a-f，A-F），允许前导零。Java实现（逐段校验）：```javapublicStringvalidIPAddress(StringqueryIP){if(queryIP.contains(".")){returncheckIPv4(queryIP);}elseif(queryIP.contains(":")){returncheckIPv6(queryIP);}else{return"Neither";}}privateStringcheckIPv4(Stringip){String[]parts=ip.split("\\.",-1);//-1保留空段if(parts.length!=4)return"Neither";for(Stringpart:parts){if(part.length()==0||part.length()>3)return"Neither";if(part.charAt(0)=='0'&&part.length()!=1)return"Neither";//前导零if(!part.matches("[0-9]+"))return"Neither";//非数字intnum=Integer.parseInt(part);if(num<0||num>255)return"Neither";}return"IPv4";}privateStringcheckIPv6(Stringip){String[]parts=ip.split(":",-1);if(parts.length!=8)return"Neither";Stringhexdigits="0123456789abcdefABCDEF";for(Stringpart:parts){if(part.length()<1||part.length()>4)return"Neither";for(charc:part.toCharArray()){if(hexdigits.indexOf(c)==-1)return"Neither";}}return"IPv6";}```关键点：s