题意理解
给定 source 字符串、pattern 字符串(保证是 source 的子序列)和可删除下标集合 targetIndices。求最多能删除多少个 targetIndices 中的字符,同时保证 pattern 仍是剩余字符串的子序列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
转化问题: 最多能删除多少 = K - 最少需要保留多少
"最少需要保留多少"指:在 targetIndices 中,至少需要保留多少个字符才能保证 pattern 是子序列。
使用动态规划。
设 dp[i][j]dp[i][j]dp[i][j] 表示:匹配 pattern 的前 jjj 个字符,只考虑 source 的前 iii 个位置,最少需要保留多少个 targetIndices 中的字符。
状态转移:
1. 不用 source[i-1] 匹配:dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j]dp[i][j]=dp[i−1][j]
2. 用 source[i-1] 匹配 pattern[j-1](需字符相同):
* 若 i−1i-1i−1 在 targetIndices 中:dp[i][j]=min(dp[i][j],dp[i−1][j−1]+1)dp[i][j] = \min(dp[i][j], dp[i-1][j-1] + 1)dp[i][j]=min(dp[i][j],dp[i−1][j−1]+1)
* 否则:dp[i][j]=min(dp[i][j],dp[i−1][j−1])dp[i][j] = \min(dp[i][j], dp[i-1][j-1])dp[i][j]=min(dp[i][j],dp[i−1][j−1])
边界条件:
* dp[i][0]=0dp[i][0] = 0dp[i][0]=0:匹配空 pattern 不需要保留任何字符
* dp[0][j]=∞dp[0][j] = \inftydp[0][j]=∞(j>0j > 0j>0):空 source 无法匹配非空 pattern
答案: K−dp[n][m]K - dp[n][m]K−dp[n][m]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码