680. Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba" Output: True

Example 2:

Input: "abca" Output: True Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

1. 브루트포스 풀이 (시간 초과)

처음에 이렇게 풀었더니 시간 초과가 나왔다. 배열의 길이가 O(n)인데 매번 for문 안에서 새로운 배열을 만들어주는 것 (t)도 O(n)의 시간이 되어 전체 O(n^2)의 시간이 된다.

class Solution(object):
    def validPalindrome(self, s):
        for i in xrange(len(s)):
            t = s[:i] + s[i+1:]
            if t == t[::-1]: return True

        return s == s[::-1]

2. 그리디 풀이 

첫 원소와 마지막 원소를 비교해나가면서 다르다면 첫 원소나 마지막 원소를 삭제했을 때도 다를 때는 결코 펠린드롬 문자열이 될 수 없으므로 False를 리턴하고 하나라도 펠린드롬이 될 경우 True를 반환한다.

class Solution:
    def validPalindrome(self, s: str) -> bool:
        if s==s[::-1]: return True
        i=0
        while i<=len(s)/2 and s[i]==s[-(i+1)]: #첫 원소와 끝 원소가 다르면 첫 원소, 마지막 원소를 삭제해본다.
            i+=1
        s=s[i:len(s)-i] # O(n)
        return s[1:]==s[1:][::-1] or s[:-1]==s[:-1][::-1] # 첫원소 삭제했을 때나 마지막원소를 삭제
        # 둘 중 하나가 펠린드롬이 나오지 않으면 무조건 False이다.