[Swift]LeetCode392. 判断子序列 | Is Subsequence

原文地址：https://www.cnblogs.com/strengthen/p/10299618.html 

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code? 

---

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

后续挑战 :

如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

---

Runtime: 132 ms

Memory Usage: 25.1 MB

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        if s == "" { return true }
        else if t == "" { return false }
        
        var arrayS = [Character](s)
        var arrayT = [Character](t)
        
        func helper(arrayS: [Character], arrayT: [Character], startS: Int, startT: Int) -> Bool {
            
            for i in startT ..< arrayT.count {
                if arrayS[startS] == arrayT[i] {
                    if startS == arrayS.count - 1 {
                        return true
                    } else {
                        return helper(arrayS: arrayS, arrayT: arrayT, startS: startS + 1, startT: i + 1)    
                    }
                }
            }
            return false
        }
        return helper(arrayS: arrayS, arrayT: arrayT, startS: 0, startT: 0)    
        
    }
}

---

144ms

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        var i = 0
        var longstr = Array(t)
        for char in s {
            while i < longstr.count && longstr[i] != char {
                i += 1
            }
            
            if i >= longstr.count {
                return false
            }
            i += 1
        }
        return true
    }
}

---

156ms

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        guard s.count <= t.count else { return false }
        
        let arrS = Array(s)
        let arrT = Array(t)
        
        var i = 0;
        var j = 0;
        
        while i < arrS.count && j < arrT.count {
            if arrS[i] == arrT[j] {
                i += 1
                j += 1
            } else {
                j += 1
            }
        }
        
        return i == arrS.count
    }
}

---

160ms

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        let arrS = Array(s)
        let arrT = Array(t)

        var sum = 0
        var lastj = 0
        for i in 0..<arrS.count {
            for j in lastj..<arrT.count {
                if arrS[i] == arrT[j] {
                    lastj = j+1
                    sum += 1
                    break
                }
            }
            if sum <= i {
                return false
            }
        }
        return sum == arrS.count
    }
}

---

164ms

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        guard s != "" else { return true }
        var i = 0
        var j = 0
        let s = Array(s)
        let t = Array(t)
        while i < s.count, j < t.count {
            if s[i] == t[j] {
                i += 1
            }
            j += 1
        }
        return i == s.count
    }    
}

---

192ms

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        return isSubsequenceIteration(s, t)
    }
    
    func isSubsequenceIteration(_ s: String, _ t: String) -> Bool {
        guard !s.isEmpty else { return true }
        guard !t.isEmpty else { return false }
        
        let sArray = Array(s)
        let tArray = Array(t)
        
        var hash = [String:Int]()
        var current = 0
        
        for character in tArray {
            if sArray[current] == character {
                current += 1
                if current == sArray.count {
                    return true
                }
            }
        }
        
        return false
    }
}

---

232ms

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        if s.isEmpty {
            return true
        }
        var result = false
        var sIx = s.startIndex
        var sCh = s[sIx]
        for tCh in t {
            if tCh == sCh {
                // found it, go to next char
                sIx = s.index(after: sIx)
                if sIx == s.endIndex {
                    //found them all
                    result = true  
                    //no need to keep going
                    break 
                }
                sCh = s[sIx]
            }
        }
        return result
    }
}

---

460ms

class Solution {
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        var s = Array(s)
        s.reverse()
        var t = Array(t)
        t.reverse()
        while (s.count > 0 && t.count > 0) {
            var sLast = s[s.count-1]
            var tLast = t[t.count-1]
            if sLast == tLast{
                s.removeLast()
            }
            t.removeLast()
        }
        return s.count == 0
    }
}