[Swift]LeetCode1312. 让字符串成为回文串的最少插入次数 | Minimum Insertion Steps to Make a String Palindrome
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.
A Palindrome String is one that reads the same backward as well as forward.
Example 1:
Input: s = "zzazz" Output: 0 Explanation: The string "zzazz" is already palindrome we don't need any insertions.
Example 2:
Input: s = "mbadm" Output: 2 Explanation: String can be "mbdadbm" or "mdbabdm".
Example 3:
Input: s = "leetcode" Output: 5 Explanation: Inserting 5 characters the string becomes "leetcodocteel".
Example 4:
Input: s = "g" Output: 0
Example 5:
Input: s = "no" Output: 1
Constraints:
1 <= s.length <= 500- All characters of
sare lower case English letters.
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入：s = "zzazz" 输出：0 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = "mbadm" 输出：2 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：
输入：s = "leetcode" 输出：5 解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
示例 4：
输入：s = "g" 输出：0
示例 5：
输入：s = "no" 输出：1
提示：
1 <= s.length <= 500s中所有字符都是小写字母。
Runtime: 300 ms
Memory Usage: 21.9 MB
1 class Solution {
2 var memo:[[Int]]!
3 func minInsertions(_ s: String) -> Int {
4 let s = Array(s)
5 memo = [[Int]](repeating: [Int](repeating: -1, count: s.count), count: s.count)
6 return dp(s,0,s.count - 1)
7 }
8
9 func dp(_ s:[Character],_ i:Int,_ j:Int) -> Int
10 {
11 //Base case.
12 if i >= j
13 {
14 return 0
15 }
16 //Check if we have already calculated the value for the pair `i` and `j`.
17 if memo[i][j] != -1
18 {
19 return memo[i][j]
20 }
21 //Recursion as mentioned above.
22 memo[i][j] = s[i] == s[j] ? dp(s,i+1,j-1) : 1 + min(dp(s,i+1,j),dp(s,i,j-1))
23 return memo[i][j]
24 }
25 }