LintCode 49 [Sort Letters by Case]

原题

给定一个只包含字母的字符串，按照先小写字母后大写字母的顺序进行排序。

给出"abAcD"，一个可能的答案为"acbAD"

小写字母或者大写字母他们之间不一定要保持在原始字符串中的相对位置。
在原地扫描一遍完成

解题思路

• Two Pointers - 对撞型指针问题
• 做指针和右指针指向的字母，可能出现四种情况需要考虑：
• 左：小写 | 右：小写 ====> 左指针左移
• 左：大写 | 右：小写 ====> 交换字母
• 左：大写 | 右：大写 ====> 右指针右移
• 左：小写 | 右：小写 ====> 左指针左移，右指针右移

完整代码

class Solution:
    """
    @param chars: The letters array you should sort.
    """
    def sortLetters(self, chars):
        if not chars or len(chars) < 2:
            return chars
            
        left, right = 0, len(chars) - 1
        while left < right:
            if ord(chars[left]) < 96 and ord(chars[right]) > 96:
                chars[left], chars[right] = chars[right], chars[left]
            elif ord(chars[left]) < 96 and ord(chars[right]) < 96:
                right -= 1
            elif ord(chars[left]) > 96 and ord(chars[right]) > 96:
                left += 1
            else:
                left += 1 
                right -= 1