CrackingTheCode-Chap1.swift

import UIKit

//1.1

extension String {
    
    ///Implement an algorithm to determine if a string has all unique characters.
    ///What if you cannot use additional data structures
    public func hasUniqueCharacter(useAdditionalDataStructures: Bool = true) -> Bool {
        
        if useAdditionalDataStructures {
            
            //O(n) time
            var set = Set<Character>()
            for c in self.characters {
                
                if set.contains(c) {
                    return false
                } else {
                    set.insert(c)
                }
            }
            
            return true
            
        } else {
            
            //O(n^2)
            var i = 0
            for ci in self.characters {
                
                let sub = self.substringWithRange(Range<String.Index>(start: self.startIndex.advancedBy((i++)+1), end: self.endIndex))
                for cj in sub.characters {
                    if cj == ci { return false }
                }
            }
            
            return true
        }
      
    }
}

"abcde".hasUniqueCharacter(true)
"abcda".hasUniqueCharacter(true)
"abcde".hasUniqueCharacter(false)
"abcda".hasUniqueCharacter(false)

//1.2

extension String {
    
    func reverse() -> String {
        return self.characters.reduce("") { String($1) + $0 }
    }
}

"abcd".reverse()

//1.3

extension String {
    
    ///Given two strings, write a method to decide if one is a permutation of the other.
    public func isPermutation(other: String) -> Bool {
    
        var map = [Character: Int]()
 
        //O(n)
        for c in self.characters {
            if let value = map[c] { map[c] = value + 1
            } else { map[c] = 1 }
        }
        
        //O(n)
        for c in other.characters {
            if let value = map[c] { map[c] = value - 1
            } else { return false }
        }
        
        //O(n)
        for (_, value) in map {
            if value != 0 { return false }
        }
        
        return true
    }
    
}

"abc".isPermutation("cba")
"abc".isPermutation("dba")
"abc".isPermutation("aabc")
"abc".isPermutation("bac")

// 1.5

extension String {
    
    ///Write a method to replace all spaces in a string with'%20'. 
    //You may assume that the string has sufficient space at the end of the string to hold the additional characters, 
    //and that you are given the "true" length of the string. (Note: if imple- menting in Java, please use a character array 
    //so that you can perform this operation in place.)
    func replaceSpaces() -> String {
        return self.characters.reduce("") {
            if $1 == " " { return $0 + "%20"
            } else { return $0 + String($1) }
        }
    }
}

"Hello how are you".replaceSpaces()


//1.5

extension String {
    
    ///Implement a method to perform basic string compression using the counts of repeated characters. 
    ///For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not 
    ///become smaller than the original string, your method should return the original string.
    public func compress() -> String {
        
        var result = ""
        
        var idx = 0
        var count = 1
        
        for ci in self.characters {
            
            if count > 1 {
                count--
            
            } else {
                
                for cj in self.substringWithRange(Range<String.Index>(start: self.startIndex.advancedBy(idx+1), end: self.endIndex)).characters {
                    
                    //compare the characters
                    if cj == ci {
                        count++
                    } else {
                        break
                    }
                }
                
                idx += count
                result += "\(ci)\(count)"
            }
        }
        
        return result.lengthOfBytesUsingEncoding(NSUTF8StringEncoding) < self.lengthOfBytesUsingEncoding(NSUTF8StringEncoding) ? result : self
        
    }
}

"aaaaaabbbcc".compress()
"abc".compress()
"aabbccc".compress()


//1.7

extension Array where Element: Array<Int> {
    
    public func zeroRowAndColumn() -> Void {
        
        var result = Array(self)
        
        func zero(i: Int, j: Int) {
            for m = result.count-1; m >= 0; m-- { result[m][j] = 0 }
            for m = result[i].count-1; m >= 0; m-- { result[i][m] = 0 }
        }
        
        for i = 0; i < self.count; i++ {
            for j = 0; j < self[i].count; j++ {
                if self[i][j] == 0 { zero(i: i, j: j) }
            }
        }
        
        return result
    }
    
}


//1.8


extension String {
    
    ///Assume you have a method isSubstring which checks if one word is a substring of another.
    //Given two strings, s i and s2, write code to check if s2 is a rotation of si using only one call to isSubstring 
    //(e.g.,"waterbottle"is a rota- tion of "erbottlewat").
    public func isRotation(other: String) -> Bool {
        return (self + self).containsString(other)
    }
}

"waterbottle".isRotation("erbottlewat")
"a".isRotation("b")