這是悅樂書的第353次更新，第378篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級別的第215題（順位題號是917）。給定一個字符串S，返回“反向”字符串，其中所有非字母的字符都保留在同一位置，并且所有字母都反轉其位置。例如：

輸入：“ab-cd”
輸出：“dc-ba”

輸入：“a-bC-dEf-ghIj”
輸出：“j-Ih-gfE-dCba”

輸入：“Test1ng-Leet = code-Q！”
輸出：“Qedo1ct-eeLg = ntse-T！”

注意：

• S.length <= 100

• 33 <= S[i].ASCIIcode <= 122

• S不包含\或“
  
  

02 第一種解法

使用雙指針。

定義兩個指針i和j，一個從前往后，一個從后往前，只有兩個指針所在元素都是字母時才交換位置，如果其中一個不是字母，就向前前進一步繼續判斷，如果兩個指針所在元素都不是字母就同時向前移動。

此解法的時間復雜度是O(N)，空間復雜度是O(N)。

public String reverseOnlyLetters(String S) {int i = 0, j = S.length()-1;char[] arr = S.toCharArray();while (i < j) {char c = arr[i];char c2 = arr[j];if (Character.isLetter(c) && Character.isLetter(c2)) {arr[i] = c2;arr[j] = c;i++;j--;} else if (!Character.isLetter(c) && Character.isLetter(c2)) {i++;} else if (Character.isLetter(c) && !Character.isLetter(c2)) {j--;} else if (!Character.isLetter(c) && !Character.isLetter(c2)) {i++;j--;}}return new String(arr); }

03 第二種解法

在雙指針的基礎上做了下變動，使用StringBuilder來拼接新的字符，但是雙指針的思路沒變。

此解法的時間復雜度是O(N)，空間復雜度是O(N)。

public String reverseOnlyLetters2(String S) {int j = S.length()-1, n = S.length();StringBuilder sb = new StringBuilder();for (int i=0; i<n; i++) {if (Character.isLetter(S.charAt(i))) {while (j>=0 && !Character.isLetter(S.charAt(j))) {j--;}sb.append(S.charAt(j--));} else {sb.append(S.charAt(i));}}return sb.toString(); }

04 第三種解法

利用棧，借助其先進后出的特性。

先將S中的字母全部入棧，然后再遍歷S中的字符，如果是字母，就從棧頂取一位元素出來拼接，不是字母，就直接拼接當前元素。

此解法的時間復雜度是O(N)，空間復雜度是O(N)。

public String reverseOnlyLetters3(String S) {Stack<Character> stack = new Stack<Character>();char[] arr = S.toCharArray();for (char c : arr) {if (Character.isLetter(c)) {stack.push(c);}}StringBuilder sb = new StringBuilder();for (char c : arr) {if (Character.isLetter(c)) {sb.append(stack.pop());} else {sb.append(c);}}return sb.toString(); }

05 小結

算法專題目前已連續日更超過六個月，算法題文章221+篇，公眾號對話框回復【數據結構與算法】、【算法】、【數據結構】中的任一關鍵詞，獲取系列文章合集。

以上就是全部內容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支持！

轉載于:https://www.cnblogs.com/xiaochuan94/p/11020782.html

總結

以上是生活随笔為你收集整理的LeetCode.917-只反转字母(Reverse Only Letters)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。