Leetcode: Reverse Only Letters

Reverse Only Letters



Similar Problems:


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 “

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/reverse-only-letters
// Basic Ideas: Two pointer
// Complexity: Time O(n), Space O(n)
//   If given a list, instead of string, space complexity can be O(1)
func isLetter(ch byte) bool {
    if ch >= byte('a') && ch <= byte('z') { return true }
    if ch >= byte('A') && ch <= byte('Z') { return true }
    return false
}

func reverseOnlyLetters(S string) string {
    bytes := []byte(S)
    l, r := 0, len(bytes)-1
    for l<r {
        b1, b2 := bytes[l], bytes[r]
        if !isLetter(b1) {
            l++
            continue
        }
        if !isLetter(b2) {
            r--
            continue
        }
        bytes[l], bytes[r] = bytes[r], bytes[l]
        l, r = l+1, r-1
    }
    return string(bytes)
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.