LeetCode上几道和字符串有关的动态规划问题

Word Break

题意

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。 给出

s = “leetcode”,dict = [“leet”,”code”],返回 true 因为“leetcode”可以被空格切分成“leet code”

思路

凡是和字符串有关的题,在应用动态规划方法时主要有两种思路:

  • dp[i][j]表示子串s[i,j]满足某一要求
  • dp[i]表示子串s[0,i]满足某一要求

本题中选择第二种思路,即用dp[i]表示字符串的(0, i)之间的子串是否可以被空格切分成一个或多个出现在字典中的单词,那么对于dp[j](j > i),如果s[i,j]代表的子串在词典中出现过,并且dp[i] = true,则有dp[j] = true

实现

 

Word Break II

题意

给出一字串s和单词的字典dict,在字符串中增加空格来构建一个句子,并且所有单词都来自字典, 返回所有有可能的句子。 如

思路

我们观察到,这道题很明显是需要判断s[i,j]是否满足某一条件,所以思路二比较符合。另外我们在前一篇博客中也提到

如果题目要求所有符合某一条件的集合,那么就可以考虑用回溯法来解决。

因此本题我们可以使用二维动态规划,配合回溯法来解决。

实现

最长回文子串

题意

给定一个字符串s,找出s中的最长回文子串。如输入s = “bacad”,返回”aca”。

思路

我们看到实例中的”aca”是位于s的中部的,因此思路二显然不太适合,所以我们可以想办法往思路一上凑凑。我们可以用dp[j][i]表示s[j,i]是否是一个回文串,那么计算dp的方法如下:

dp[j][i] = (s[j] == s[i] && (i - j < 2 || dp[j+1][i-1])

实现

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据