917.Reverse-Only-Letters.md

917. Reverse Only Letters

---

题目地址

https://leetcode.com/problems/reverse-only-letters/

题目描述

Given a string S, return the "reversed" string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:
Input: "ab-cd"
Output: "dc-ba"

Example 2:
Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:
Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"
 

Note:
S.length <= 100
33 <= S[i].ASCIIcode <= 122 
S doesn't contain \ or "

代码

Approach #1 Stack

Time Complexity & Space Complexity: O(N)

class Solution {
  public String reverseOnlyLetters(String S) {
		Stack<Character> letters = new Stack();
    for (char c : S.toCharArray()) {
      if (Character.isLetter(c)) {
        letters.push(c);
      }
    }
    
    StringBuilder ans = new StringBuilder();
    for (char c : S.toCharArray()) {
      if (Character.isLetter(c)) {
        ans.append(letters.pop());
      } else {
        ans.append(c);
      }
    }
    
    return asn.toString();
  }
}

Approach #2 Reverse Pointer

Time Complexity & Space Complexity: O(N)

class Solution {
  public String reverseOnlyLetters(String S) {
    StringBuilder ans = new StringBuilder();
    int j = S.length() - 1;
    for (int i = 0; i < S.length(); i++) {
      if (Character.isLetter(S.charAt(i))) {
        while (!Character.isLetter(S.charAt(j))) {
          j--;
        }
        ans.append(S.charAt(j--));
      } else {
        ans.apend(S.charAt(i));
      }
    }
    return ans.toString();
  }
}