Swift solution - Binary Search


  • 0
    class Solution {
        func isSubsequence(_ s: String, _ t: String) -> Bool {
            let sCharacters = Array(s.characters)
            let tCharacters = Array(t.characters)
            var index = [[Int]](repeatElement([Int](), count: 256))
            var prev = 0
            
            for i in 0..<tCharacters.count {
                let asciiValue = String(tCharacters[i]).asciiValueOfCharacter
                index[asciiValue].append(i)
            }
            for i in 0..<sCharacters.count {
                let asciiValue = String(sCharacters[i]).asciiValueOfCharacter
                if index[asciiValue].count == 0 {
                    return false
                }
                var j = binarySearch(index[asciiValue], prev)
                if j < 0 {
                    j = -j - 1
                }
                if j == index[asciiValue].count {
                    return false
                }
                prev = index[asciiValue][j] + 1
            }
            
            return true
        }
        
        private func binarySearch(_ nums: [Int], _ target: Int) -> Int {
            var left = 0
            var right = nums.count - 1
            var middle = 0
            
            while left <= right {
                middle = (left + right) / 2
                if nums[middle] < target {
                    left = middle + 1
                } else {
                    right = middle - 1
                }
            }
            
            return left
        }
    }
    
    extension String {
        var asciiValueOfCharacter: Int {
            get {
                let value = self.unicodeScalars.filter{$0.isASCII}.first?.value ?? 0
                return Int(value) 
            }
        }
    }
    

Log in to reply
 

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