題目

難度：★☆☆☆☆
類型：字符串

給定一個(gè)字符串 S，返回 “反轉(zhuǎn)后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置發(fā)生反轉(zhuǎn)。

提示
S.length <= 100
33 <= S[i].ASCIIcode <= 122
S 中不包含 \ or "

示例

示例 1
輸入："ab-cd"
輸出："dc-ba"

示例 2
輸入："a-bC-dEf-ghIj"
輸出："j-Ih-gfE-dCba"

示例 3
輸入："Test1ng-Leet=code-Q!"
輸出："Qedo1ct-eeLg=ntse-T!"

解答

方案1：哈希表

我們使用字典記錄每個(gè)字符所在的位置，然后找出所有字母字符的位置并組成列表，將該列表逆序更新原字典，相當(dāng)于只在有字母的位置上做字符串逆序，使用更新后的字典構(gòu)建字母逆序的字符串。

class Solution:
    def reverseOnlyLetters(self, S):
        """
        :param S: str
        :return: str
        """
        loc = {i: c for i, c in enumerate(S)}
        alpha = {i: c for i, c in loc.items() if c.isalpha()}
        reversed_alpha = {i: c for i, c in zip(reversed(list(alpha.keys())), alpha.values())}
        loc.update(reversed_alpha)
        return ''.join([loc[i] for i in range(len(S))])

方案2：雙指針

我們定義左右指針，并初始化為字符串兩端字符所在位置，然后兩個(gè)指針逐漸向中間靠攏，當(dāng)兩個(gè)指針同時(shí)找到字母時(shí)，交換兩指針處的字符，如果只有一個(gè)指針處是字母，那么另一個(gè)指針要繼續(xù)移動(dòng)，直到找到字母。循環(huán)控制條件是左指針不能到右指針右邊。

class Solution:
    def reverseOnlyLetters(self, S):
        """
        :param S: str
        :return: str
        """

        S = list(S)
        left, right = 0, len(S)-1
        while left < right:
            if not S[left].isalpha():
                left += 1
            elif not S[right].isalpha():
                right -= 1
            else:
                S[left], S[right] = S[right], S[left]
                left += 1
                right -= 1
        return ''.join(S)

如有疑問或建議，歡迎評(píng)論區(qū)留言~