LeetCode – 392. Is Subsequence

題目連結:

https://leetcode.com/problems/is-subsequence/

參考解法:

https://leetcode.com/problems/is-subsequence/discuss/394509/Swift-solution-32ms-100-very-simple

Test cases:

// s: “", t: “a"
// s: “a", t: “"
// s: “abc", t: “abc"
// s: “abc", t: “abdce" note: 多字
// s: “abc", t: “adc" note: 少字
// s: “abbc",t: “abcb" note: 順序錯

法ㄧ

Time complexity: O(mn) 、Space complexity: O(n)

Note: m is the length of s, n is the length of t

    func isSubsequence(_ s: String, _ t: String) -> Bool {
        if s.isEmpty { return true }
        else if !s.isEmpty && t.isEmpty { return false }
        else if s == t { return true }
        else {
            let tArr = Array(t)
            var lastPos = 0
            for c in s {
                var found = false
                for i in lastPos ..< tArr.count {
                    if c == tArr[i] {
                        if i < lastPos {
                            return false
                        }
                        found = true
                        lastPos = i + 1
                        break
                    }
                }
                if !found { return false }
            } 
            return true
        }
    }

法二

Time complexity: O(m) 、Space complexity: O(n+m)

Note: m is the length of s, n is the length of t

    func isSubsequence(_ s: String, _ t: String) -> Bool {
        let sArr = Array(s)
        let tArr = Array(t)
        var sIndex = 0
        var tIndex = 0
        while sIndex < sArr.count && tIndex < tArr.count {
            if sArr[sIndex] == tArr[tIndex] {
                sIndex += 1
            }
            tIndex += 1
        }
        return sIndex == s.count
    }