[swift]DP
\n// https://leetcode.com/problems/find-all-good-strings/\nclass Solution {\n    //\u7528\u4E8E\u6570\u4F4DDP\n    private let lowercases = [Character]("abcdefg
```\n// https://leetcode.com/problems/find-all-good-strings/\nclass Solution {\n    //\u7528\u4E8E\u6570\u4F4DDP\n    private let lowercases = [Character]("abcdefghijklmnopqrstuvwxyz")\n    private var charToIndex = [Character:Int]()\n    private let MOD = 1_000_000_007\n\n    // evil \u76F8\u5173\u4FE1\u606F\n    private var M = -1\n    private var evilPreffixes = [String]()\n    private var evilChars = [Character]()\n    private var charToLength = [Character:[Int]]()\n\n\n    init() {\n        for ch in lowercases {\n            let idx = Int(ch.asciiValue! - 97)\n            charToIndex[ch] = idx\n        }\n    }\n    func findGoodStrings(_ n: Int, _ s1: String, _ s2: String, _ evil: String) -> Int {\n        guard s1 <= s2 else {\n            return 0\n        }\n        guard s1 < s2 else {\n            return s1.contains(evil) ? 0 : 1\n        }\n        caculateEvilInfos(of: evil)\n        return (helper(s2, n, evil) - helper(s1, n, evil) + MOD + (s1.contains(evil) ? 0 : 1)) % MOD\n    }\n\n    private func caculateEvilInfos(of evil: String) {\n        self.M = evil.count\n        self.evilPreffixes = (0...M).map ({ String(evil.prefix($0))})\n        self.evilChars = [Character](evil)\n        for i in 0..<M {\n            charToLength[evilChars[i],default: []].append(i + 1)\n        }\n    }\n\n\n\n    private func getMatchedLength(_ str: String) -> Int {\n\n        let last = str.last!\n\n        guard let lengths = charToLength[last] else {return 0}\n\n        var j = lengths.count - 1\n        while j >= 0 {\n            if str.hasSuffix(evilPreffixes[lengths[j]]) {\n                break\n            }\n            j -= 1\n        }\n        return j == -1 ? 0 : lengths[j]\n    }\n\n\n\n    private func helper(_ upperBound: String, _ n: Int, _ evil:String) -> Int {\n\n        let upperBoundPreffixes = (0...n).map { String(upperBound.prefix($0))}\n        let upperBoundChars = [Character](upperBound)\n        let N = upperBound.count\n\n        var memo = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: -1, count: 2), count: M), count: N)\n\n        func dfs(_ idx: Int,_ pre: String, _ matchedLength: Int, _ isLessThan: Bool) -> Int {\n            guard idx < n else {\n                return 1\n            }\n            guard -1 == memo[idx][matchedLength][isLessThan ? 1 : 0] else {\n                return memo[idx][matchedLength][isLessThan ? 1 : 0]\n            }\n\n            var ans = 0\n\n            let rightLimit = isLessThan ? 25 : charToIndex[upperBoundChars[idx]]!\n\n            for j in 0...rightLimit {\n                let s = pre + "\\(lowercases[j])"\n                guard isLessThan || s <= upperBoundPreffixes[s.count] else {\n                    continue\n                }\n                // let l = lowercases[j] == evilChars[matchedLength] ? (matchedLength + 1) : getMatchedLength(s)\n                let l = getMatchedLength(s)\n                guard l != M else {\n                    continue\n                }\n                ans += dfs(idx + 1, s, l, isLessThan || s < upperBoundPreffixes[s.count] )\n                ans %= MOD\n            }\n            memo[idx][matchedLength][isLessThan ? 1 : 0]  = ans\n            return ans\n        }\n        return dfs(0,"", 0,false)\n    }\n}\n```
['Dynamic Programming', 'Memoization', 'Swift']