word break
...j j
l e e t c o d e x
i i
0 1 2 3 4 5 6 7 8
[i, j)
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] canBreak = new boolean[s.length()+1];
canBreak[0] = true;
for (int j = 1; j <= s.length(); j++) {
for (int i = 0; i <= j; i++) {
if (canBreak[i] && wordDict.contains(s.substring(i, j))) {
canBreak[j] = true;
break;
}
}
}
return canBreak[s.length()];
}
}
word break ii
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Map<String, List<String>> memo = new HashMap<>();
return dfs(memo, s, wordDict);
}
private List<String> dfs(Map<String, List<String>> memo, String s, List<String> dict) {
if (memo.containsKey(s)) return memo.get(s);
List<String> rst = new ArrayList<>();
for (int i = 1; i <= s.length(); i++) {
String s1 = s.substring(0, i);
String s2 = s.substring(i);
if (!dict.contains(s1)) continue;
List<String> s2_phrases = dfs(memo, s2, dict);
// "a" + "b c d", "a" + "bc d", "a" + "b cd"
//1. add s1 and all combinations in s2
//2. add only s1, when s1 is full words
if (s1.length() == s.length()) {
rst.add(s1);
} else {
for (String phrase : s2_phrases) {
rst.add(s1 + " " + phrase);
}
}
}
memo.put(s, rst);
return rst;
}
}
palindrome partitioning ii
- word break + palindrome init dp
class Solution {
public int minCut(String s) {
int[] dp = new int[s.length()+1];
boolean[][] isPalin = initPalin(s);
dp[0] = 0;
for (int i = 1; i <= s.length(); i++) {
dp[i] = Integer.MAX_VALUE - 1;
}
for (int j = 1; j <= s.length(); j++) {
for (int i = 0; i < j; i++) {
if (isPalin[i][j-1]) {
dp[j] = Math.min(dp[j], dp[i] + 1);
}
}
}
return dp[s.length()] - 1;
}
private boolean[][] initPalin(String s) {
char[] chars = s.toCharArray();
int len = s.length();
boolean[][] isPalin = new boolean[len][len];
for (int i = 0; i < len; i++) {
isPalin[i][i] = true;
}
for (int i = 0; i < len - 1; i++) {
isPalin[i][i+1] = chars[i] == chars[i+1];
}
for (int j = 2; j < len; j++) {
for (int i = 0; i <= j-2; i++) { // notice "="
isPalin[i][j] = isPalin[i+1][j-1] && chars[i] == chars[j];
}
}
return isPalin;
}
}
climbing stairs
n = 4
n = 0 1 2 3 4
ways = 1 1 2 3 5
class Solution {
public int climbStairs(int n) {
int[] ways = new int[n + 1];
if (n <= 1) {
return 1;
}
ways[0] = 1;
ways[1] = 1;
for (int i = 2; i <= n; i++) {
ways[i] = ways[i - 1] + ways[i - 2];
}
return ways[n];
}
}
decode ways
class Solution {
public int numDecodings(String s) {
int len = s.length();
if (len == 0) return 0;
int[] ways = new int[len+1];
// way[n] 表示 这n个数字可以有多少ways
// idx: 0, 1, 2, 3
// input: 1, 7, 4
// f(n) = f(n - 1) when substring(n-1, n) not 0 + f(n - 2) when substring(n-2, n) is valid
// f(3) = f(2) when ("4") is not 0 + f(1) when ("74") is valid
ways[0] = 1;
for (int i = 1; i <= len; i++) {
// current case can not be 0
if (s.charAt(i-1) != '0')
ways[i] += ways[i - 1];
if (i >= 2) {
int num = (s.charAt(i-2) - '0') * 10 + s.charAt(i-1) - '0';
if (num >= 10 && num <= 26)
ways[i] += ways[i - 2];
}
}
return ways[len];
}
}
decode ways ii
public class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
final int mod = 1000000007;
int n = s.length();
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = 0;
if (s.charAt(i - 1) == '*') {
f[i] = (int)((f[i] + 9L * f[i - 1]) % mod);
if (i >= 2) {
if (s.charAt(i - 2) == '*') {
f[i] = (int)((f[i] + 15L * f[i - 2]) % mod); // notice: not 26L
}
else if (s.charAt(i - 2) == '1') {
f[i] = (int)((f[i] + 9L * f[i - 2]) % mod);
}
else if (s.charAt(i - 2) == '2') {
f[i] = (int)((f[i] + 6L * f[i - 2]) % mod);
}
}
}
else {
if (s.charAt(i - 1) != '0') {
f[i] = (f[i] + f[i - 1]) % mod;
}
if (i >= 2) {
if (s.charAt(i - 2) == '*'){
if (s.charAt(i - 1) <= '6') {
f[i] = (int)((f[i] + 2L * f[i - 2]) % mod);
}
else {
f[i] = (f[i] + f[i - 2]) % mod;
}
}
else {
int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
if (twoDigits >= 10 && twoDigits <= 26) {
f[i] = (f[i] + f[i - 2]) % mod;
}
}
}
}
}
return f[n];
}
}
edit distance:
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// 1. A[m-1] = B[n-1]: f[m][n] = min(f[m-1][n-1], f[m-1][n] + 1, f[m][n-1] + 1)
// 2. A[m-1] != B[n-1]: f[m][n] = min(f[m-1][n-1] + 1, f[m-1][n] + 1, f[m][n-1] + 1)
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) { // last word match
// dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
dp[i][j] = dp[i-1][j-1]; // dp[i-1][j-1] always the min among the three, since the assumption is dp[][] is the min operation, any dp[][..-1] or dp[..-1][] would be <= dp[][]
} else {
dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
}
}
}
return dp[m][n];
}
}
edit distance ii:
- within one edit distance
class Solution {
public boolean isOneEditDistance(String s, String t) {
int m = s.length();
int n = t.length();
if (Math.abs(m - n) > 1) return false;
if (m > n)
return isOneEditDistance(t, s);
for (int i = 0; i < m; i++) {
if (s.charAt(i) != t.charAt(i)) {
if (m == n) {
return s.substring(i + 1).equals(t.substring(i + 1));
} else {
return s.substring(i).equals(t.substring(i + 1));
}
}
}
return m != n;
}
}
class Solution {
public boolean isOneEditDistance(String s, String t) {
if (s.length() > t.length()) {
return isOneEditDistance(t, s);
}
int diff = t.length() - s.length();
if (diff > 1) {
return false;
}
if (diff == 0) {
int i;
for (i = 0; i < s.length(); i++) {
if (t.charAt(i) != s.charAt(i)) {
return (s.substring(i+1).equals(t.substring(i + 1)));
}
}
// reach end but no mismatch
if (i == s.length()) return false;
}
if (diff == 1) {
for (int i = 0; i < s.length(); i++) {
if (t.charAt(i) != s.charAt(i)) {
return (s.substring(i).equals(t.substring(i + 1)));
}
}
}
return true;
}
}