palindrome.swift

/*
    A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward.
    Examples include "amor roma", "step on no pets", "kayak", "abcdcba"
    
    Next implementations are strict with capital letters, accents, punctuation, and word dividers.
*/

// 1st shot
// expensive for memory: although Array.reverse() is lazy and does not create new storage (according to documentation - Swift 2.1),
// passing it into String initializer creates an entire new copy of the source string with reversed characters
func isPalindrome(s: String) -> Bool {
    return s == String(s.characters.reverse())
}

// another try, seems here it does not make any new copy of the string, but just iterate over a ReverseRandomAccessCollection and Swift provide good optimisations on that
// (must investigate more about what's going on here exactly)
func isPalindrome(s:String) -> Bool {
    let c = s.characters
    return c.reverse().startsWith(c[s.startIndex..<s.startIndex.advancedBy(c.count/2)])
}

// iterative
func isPalindrome(s: String) -> Bool {
    var last = s.endIndex
    for i in s.startIndex..<s.startIndex.advancedBy(s.characters.count/2) {
        last = last.predecessor()
        if (s[i] != s[last]) {
            return false
        }
    }
    return true
}

// recursive
// could result in a "Maximum call stack size exceeded" error in case of very larges strings
func isPalindrome(s: String) -> Bool {
    if (s.characters.count <= 1) {
        return true
    }
    if (s[s.startIndex] != s[s.endIndex.predecessor()]) {
        return  false
    }
    return isPalindrome(s[s.startIndex.successor()..<s.endIndex.predecessor()])
}