題目連結:
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
}