Valid Palindrome II

LeetCode Problem #680

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.

Solution

func validPalindrome(_ s: inout [String], low: Int, high: Int) -> Bool {
    var low = low
    var high = high
    
    while low < high {
        if s[low] != s[high] {
            return false
        }
    
        low += 1
        high -= 1
    }
    
    return true
}

func validPalindrome(_ s: String) -> Bool {
    var s = s.map { String($0) }
    var low = 0
    var high = s.count - 1
    
    while low < high {
        if s[low] != s[high] {
            return validPalindrome(&s, low: low + 1, high: high) || validPalindrome(&s, low: low, high: high - 1)
        }
        
        low += 1
        high -= 1
    }
    
    return true
}

Things To Do Differently

1. Index characters instead of removing from front and back of string.
2. Check loop bounds.
3. Think more carefully about single deleted character.
4. Think about passing array by reference vs. a copy.
5. Pros and cons of using same function name with different signature.
6. When function returns bool, it's okay to return call to function.