这是悦乐书的第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
    
     =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
    
      stack = new Stack
     
      ();    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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！