Formatted question description: https://leetcode.ca/all/917.html

917. Reverse Only Letters (Easy)

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:

  1. S.length <= 100
  2. 33 <= S[i].ASCIIcode <= 122 
  3. S doesn't contain \ or "

Companies:
Microsoft

Related Topics:
String

Solution 1.

// OJ: https://leetcode.com/problems/reverse-only-letters/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    string reverseOnlyLetters(string S) {
        int i = 0, j = S.size() - 1;
        while (i < j) {
            while (i < j && !isalpha(S[i])) ++i;
            while (i < j && !isalpha(S[j])) --j;
            if (i < j) swap(S[i++], S[j--]);
        }
        return S;
    }
};

Java

  • class Solution {
        public String reverseOnlyLetters(String S) {
            char[] array = S.toCharArray();
            int low = 0, high = array.length - 1;
            while (low < high) {
                char c1 = array[low], c2 = array[high];
                if (Character.isLetter(c1) && Character.isLetter(c2)) {
                    array[low] = c2;
                    array[high] = c1;
                    low++;
                    high--;
                } else {
                    if (!Character.isLetter(c1))
                        low++;
                    if (!Character.isLetter(c2))
                        high--;
                }
            }
            return new String(array);
        }
    }
    
  • // OJ: https://leetcode.com/problems/reverse-only-letters/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        string reverseOnlyLetters(string S) {
            int i = 0, j = S.size() - 1;
            while (i < j) {
                while (i < j && !isalpha(S[i])) ++i;
                while (i < j && !isalpha(S[j])) --j;
                if (i < j) swap(S[i++], S[j--]);
            }
            return S;
        }
    };
    
  • class Solution(object):
        def reverseOnlyLetters(self, S):
            """
            :type S: str
            :rtype: str
            """
            letters = []
            N = len(S)
            for i, s in enumerate(S):
                if s.isalpha():
                    letters.append(s)
            res = ""
            for i, s in enumerate(S):
                if s.isalpha():
                    res += letters.pop()
                else:
                    res += s
            return res
    

All Problems

All Solutions