ac solution code


  • 0

    Two Pointer SPIRIT:
    Use start..end window to approach target progressively to get linear time complexity.

    PROCEDURE:
    In each step of while loop, decide the next direction with the below IF statements:
    If nums[start] + nums[end] == target, return result
    If nums[start] + nums[end] < target, start++ to advance start boundary
    If nums[start] + nums[end] > target, end-- to rewind end boundary

        /*
         Solution1. Two Pointers: time = O(n); space = O(n) - temperary char array
         */
        func isPalindrome(_ s: String) -> Bool {
            var s = s.lowercased()
            var chars = [Character](s.characters)
            var start = 0
            var end = chars.count - 1
            while start < end {
                while start < end, !isAlpha(chars[start]) {
                    start += 1
                }
                while start < end, !isAlpha(chars[end]) {
                    end -= 1
                }
                if chars[start] != chars[end] {
                    return false
                }
                start += 1
                end -= 1
            }
            return true
        }
        private func isAlpha(_ char: Character) -> Bool {
            guard let char = String(char).unicodeScalars.first else {
                return false
            }
            return CharacterSet.alphanumerics.contains(char)
        }
    
    
        /*
         Solution2. Regex replace: time = O(2n) = O(n); space = O(n) - temperary mutable s
         NOTE: import Cocoa (Leetcode doesn't support Cocoa importing now)
         */
        func isPalindrome(_ s: String) -> Bool {
            var s = s.lowercased()
            let regex = try! NSRegularExpression(pattern: "[^A-Za-z0-9]", options: .caseInsensitive)
            s = regex.stringByReplacingMatches(in: s, options: [], range: NSRange(0..<s.utf16.count), withTemplate: "")
            return s == String(s.characters.reversed())
        }
    

Log in to reply
 

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