IOS 算法(基础篇) ----- 判断子序列

今天看到一道子序列算法题, 给大家分享一下

如果你想知道什么题? 既然你诚心诚意的发问了, 我就大发慈悲的告诉你!

给定两个字符串s, t 判断s是否是t的子序列
附: 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串:
例如:
s = "axc", t = "ahbgxc" 返回 true.
s = "ayh", t = "ahbgxc" 返回 false.

方法1

    func isSubsequence(_ s: String, _ t: String) -> Bool {
        //将s字符串转成char数组
        var charArr = [Character](), cut = t, iterator = s.makeIterator()
        while let char = iterator.next() {
            charArr.append(char)
        }
        //循环, 条件char数组不为空
        while !charArr.isEmpty {
            //数组删除第一个元素, 并获取这个元素
            let element = charArr.removeFirst()
            //判断t中是否含有这个元素, 并获取元素下标, 不包含跳出循环
            if let index = cut.firstIndex(of: element) {
                //切割数组, 只留下下标之后的部分
                cut = cut.substring(from: cut.index(index, offsetBy: 1))
            }else {
                return false
            }
        }
        //如果都t包含s, 则charArr则会为空, 返回charArr.isEmpty是否为空数组即可
        return charArr.isEmpty
    }

方法2
循环判断, b中是否一一包含s中元素, 双指针法

    func isSubsequence(_ s: String, _ t: String) -> Bool {
        var i = 0, j = 0
        while i < s.count && j < t.count {
            let a = s.index(s.startIndex, offsetBy: i), b = t.index(t.startIndex, offsetBy: j)
            if s[a] == t[b] {
                i+=1
            }
            j+=1
        }
        return i == s.count
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)

IOS 算法合集地址