Swift O(N) Solution


  • 0
    I
    class Solution {
        func validPalindrome(_ s: String) -> Bool {
            return helper(s, deleted: false)
        }
        fileprivate func helper (_ s: String, deleted: Bool) -> Bool {
            var left = 0
            let chars = Array(s.characters)
            var right = chars.count - 1
            while left < right {
                let c1 = chars[left]
                let c2 = chars[right]
                if c1 == c2 {
                    left += 1
                    right -= 1
                } else if !deleted {
                    let leftIndex = s.characters.index(s.characters.startIndex, offsetBy: left)
                    let rightDeletedIndex = s.characters.index(s.characters.startIndex, offsetBy: right)
                    let leftDeletedIndex = s.characters.index(s.characters.startIndex, offsetBy: left + 1)
                    let rightIndex = s.characters.index(s.characters.startIndex, offsetBy: right + 1)
                    return helper(s.substring(with: leftIndex..<rightDeletedIndex), deleted: true)
                        || helper(s.substring(with: leftDeletedIndex..<rightIndex), deleted: true)
                    
                } else {
                    return false
                }
            }
            return true
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.