[Swift]DFS
swift []\nclass Solution {\n    typealias CH = Character\n    func validSequence(_ word1: String, _ word2: String) -> [Int] {\n        let l1: [CH] = Array(word
```swift []\nclass Solution {\n    typealias CH = Character\n    func validSequence(_ word1: String, _ word2: String) -> [Int] {\n        let l1: [CH] = Array(word1), l2: [CH] = Array(word2)\n        var path: Set<Int> = [], ch: [[Int]: [Int]] = [:]\n        let res = self.dfs(l1, l2, 0, 0, 1, &path, &ch)\n        return res.sorted()\n    }\n\n    private func dfs(_ l1: [CH], _ l2: [CH], _ i1: Int, _ i2: Int, _ q: Int, _ pa: inout Set<Int>, _ ch: inout [[Int]: [Int]]) -> [Int] {\n        guard q >= 0 else { return [] }\n        guard i1 < l1.count, i2 < l2.count else { return i2 >= l2.count ? Array(pa) : [] }\n        let key = [pa.count, i1, i2, q]\n        if let f = ch[key] { return f }\n\n        let res: [Int]\n        if l1[i1] == l2[i2] {\n            pa.insert(i1)\n            if i2 == l2.count - 1 { return Array(pa) }\n            else { res = self.dfs(l1, l2, i1 + 1, i2 + 1, q, &pa, &ch) }\n            pa.remove(i1)\n        } else {\n            pa.insert(i1)\n            var tmp = self.dfs(l1, l2, i1 + 1, i2 + 1, q - 1, &pa, &ch)\n            pa.remove(i1)\n            if tmp.isEmpty {\n                tmp = self.dfs(l1, l2, i1 + 1, i2, q, &pa, &ch)\n            }\n            res = tmp\n        }\n        ch[key] = res\n        return res\n    }\n}\n```
['Swift']