Leetcode 2193. Minimum Number of Moves to Make Palindrome [Python]

Greedy方式来做。只要头尾字母不一样，case 1 就可以从头出发，找一个和尾巴字母一样的字母，然后换到头部，看需要多少步；case 2同样，从尾巴出发往回走，找一个个头部字母一样的字母，换到尾部；看case 1和case 2哪种换法步数少就选哪种。然后头和尾完成了，把头尾去掉，把中间的substring重复上述过程，每次记录挪动步数就好。记得每次recursive的时候判断丢进来的substring是不是已经是回文了。

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        #s = list(s)
        self.res = 0
        def ispalin(s):
            if len(s) == 0 or len(s) == 1:return True
            i = 0
            j = len(s) - 1
            while i < j:
                if s[i] != s[j]:return False
                i += 1
                j -= 1
            return True
                
        def helper(s):
            n = len(s)
            if len(s) == 0:return self.res
            if ispalin(s):return self.res
            a = s[0]
            b = s[-1]
            if a != b:
                i = len(s)-1
                toright = 0
                j = 0
                toleft = 0
                while i != 0 and s[i] != a:
                    i -= 1
                    toright += 1
                while j != n and s[j] != b:
                    j += 1
                    toleft += 1
                    
                if toright < toleft:
                    s = s[:i] +  s[i+1:] + s[i]
                    self.res += n - 1 - i
                else:
                    s = s[j] + s[0:j] + s[j+1:]
                    self.res += j
            
            news = s[1:n-1]
            return helper(news)
        
        return helper(s)