2025年高頻string面試試題及答案1.反轉字符串中的單詞順序（含多空格處理）輸入字符串s可能包含前導、尾隨空格及多個空格分隔單詞，要求輸出反轉單詞順序后的字符串，且單詞間僅保留一個空格。思路：首先去除首尾空格，然后按空格分割成單詞數組（需處理連續(xù)空格），反轉數組后重新拼接。關鍵在于分割時過濾空字符串，并處理邊界情況。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.最長無重復字符的子串（滑動窗口優(yōu)化）給定字符串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.有效的括號字符串（多狀態(tài)校驗）給定字符串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)。關鍵點：通過上下界約束確保所有可能情況被覆蓋，避免遞歸或動態(tài)規(guī)劃的高空間消耗。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算法通過預處理（插入''）統一奇偶長度回文，利用回文對稱性優(yōu)化中心擴展。步驟：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數組）。優(yōu)勢：相比中心擴展法O(n2)，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.括號提供（回溯法優(yōu)化）數字n代表提供n對括號，輸出所有有效組合。優(yōu)化思路：回溯時跟蹤左右括號數量，僅當左括號<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)（遞歸棧深度）。擴展：動態(tài)規(guī)劃解法，dp[i]表示i對括號的有效組合，dp[i]='('+dp[j]+')'+dp[i-j-1]（j從0到i-1）。9.編輯距離（動態(tài)規(guī)劃空間優(yōu)化）給定兩個字符串word1和word2，計算將word1轉換成word2所需的最少操作數（插入、刪除、替換）。動態(tài)規(guī)劃狀態(tài)定義：dp[i][j]表示word1前i字符轉成word2前j字符的最小操作數。狀態(tài)轉移：若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（刪除、插入、替換）?？臻g優(yōu)化：用一維數組prev和curr代替二維數組。Java實現（空間優(yōu)化版）：```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)（優(yōu)化后）。關鍵點：空間優(yōu)化通過滾動數組減少內存消耗，適合處理大字符串。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，返回所有可能的回文子串分割方案（每個子串都是回文）。優(yōu)化思路：回溯時，用記憶化數組記錄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)。擴展：若要求最少分割次數，可用動態(tài)規(guī)劃，dp[i]表示前i字符的最少分割數，dp[i]=min(dp[j]+1)（j<i且s[j..i-1]是回文）。14.驗證IP地址（正則與逐段校驗）給定字符串queryIP，判斷是IPv4、IPv6還是無效。IPv4規(guī)則：4段，0-255，無前導零（除非是0）。IPv6規(guī)則：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