算法通关村第十二关白银挑战——仅仅反转英文字母问题解析

大家好，我是怒码少年小码。

今天做道经典的字符串算法题目。

仅仅反转字母

LeetCode 917：给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。
  返回反转后的 s 。

示例 1：

• 输入：s = “ab-cd”
• 输出：“dc-ba”

示例 2：

• 输入：s = “a-bC-dEf-ghIj”
• 输出：“j-Ih-gfE-dCba”

仔细想想，这道题很简单（简单到我的第一想法和力扣的官方题解是一样的。

方法一：双指针思想

我第一个想到的就是这个，要是不记得啥是双指针了请看我之前的文章：

定义两个指针left，right分别指向字符串的首尾，从两边向中间遍历。

• 如果遇到某一指针所指的字符不是英文字符就更新指针(left++或者right--)。
• 如果两个都是英文字母，就交换这两个字符。代码如下：

 string reverseOnlyLetters(string s) {
    int left = 0 ; 
    int right = s.size() - 1;
    while(left < right){
      while(left<right && !((s[left] >= 'a' && s[left] <= 'z') || (s[left] >= 'A' && s[left] <= 'Z')) ){
          left++;
      }
      while(left < right && !((s[right] >= 'a' && s[right] <= 'z') || (s[right] >= 'A' && s[right] <= 'Z')) ){
          right--;
      }

      if(left < right){
          char temp = s[left];
          s[left] = s[right];
          s[right] = temp;
          left++;
          right--;
      }
    }
    return s;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

C++中判断是否为英文字母还可以使用ASCLL码或者内置函数isalpha()。

方法二：使用栈

数据结构中的栈有 先进后出 的特点，我们可以利用这一特点，先从前往后保存一遍英文字母，然后构建结构字符串要用到英文字符的时候再拿出来。

下面这段代码我使用Java写的：

public String reverseOnlyLetters(String s) {
    char[] chars = s.toCharArray();
    Stack<Character> letters = new Stack();
    for(char c : chars){
        if(Character.isLetter(c)){
            letters.push(c);
        }
    }
    StringBuilder ans = new StringBuilder();
    for(char c: chars){
      if(Character.isLetter(c)){
          ans.append(letters.pop());
      }else{
            ans.append(c);
      }
    }
    return ans.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18