0917 Reverse Only Letters


思路 :双指针法

left从左开始扫描right从右,若是都扫到字母且 left < right,就交换s[left]s[right],然后leftright同时向中间移动一个位置,直到left >= rightright向左移动一个位置,left向右移动一个位置,直到left > right

实现

GO

func reverseOnlyLetters(s string) string {
    // go 的 string 不可变
    res := []byte(s)
    left, right := 0, len(s)-1
    for {
        for left < right && !unicode.IsLetter(rune(s[left])) {
            left++
        }
        for right > left && !unicode.IsLetter(rune(s[right])) {
            right--
        }
        // 注意是 >= 而非 >
        if left >= right {
            break
        }
        // 会习惯性的使用swap函数
        res[left], res[right] = res[right], res[left]
        left++
        right--
    }
    return string(res)
}

c++

class Solution {
public:
    string reverseOnlyLetters(string s) {
        int left = 0;
        int right = s.size()-1;

        // 最开始写的是 left < right ,似乎不太不合适
        while (true)
        {
            // PS:学到了 isalpha() 
            while( left < right && !isalpha(s[left]) )
                left++;

            while( left < right && !isalpha(s[right]) )
                right--;
            if ( left >= right )
                break;
            swap(s[left], s[right]);
            left++;
            right--;
        }
        return s;

    }
};

发表评论