LeetCode 115 · Hard · 2-D Dynamic Programming

Distinct Subsequences

Count the different ways to delete characters from s so that what is left spells t. Two ways differ if they keep a different set of positions.

O(m·n)time
O(m·n)space
use or skip a lettermemo DFS on (i, j)

lowercase letters a–z · s: 1–8 characters · t: 1–6 characters

cache cell (i, j) = ways to spell t.substring(j) from s.substring(i) · ∅ = nothing left · ∅ column = t done → 1 · ∅ row = s used up → 0

Call stack bottom → top

private String s;private String t;private Integer[][] cache;public int numDistinct(String s, String t) { this.s = s; this.t = t; cache = new Integer[s.length()][t.length()]; return dfs(0, 0);}private int dfs(int i, int j) { if (j == t.length()) { return 1; } if (i == s.length()) { return 0; } if (cache[i][j] != null) { return cache[i][j]; } if (s.charAt(i) == t.charAt(j)) { cache[i][j] = dfs(i + 1, j + 1) + dfs(i + 1, j); } else { cache[i][j] = dfs(i + 1, j); } return cache[i][j];}
i, j
—
s.charAt(i), t.charAt(j)
—
cache entries
0
memo hits
0

Why it works

  1. Brute force lists every subsequence of s (2m) and counts those equal to t.
  2. Each character of s is used or skipped. If s.charAt(i) == t.charAt(j), either let it supply t.charAt(j) (go to (i+1, j+1)) or skip it (go to (i+1, j)); the two sets of ways never overlap, so they add. If it differs, it can only be skipped.
  3. Complexity: (m+1)·(n+1) states, O(1) work each once cached: O(m·n) time and space.
  4. Pitfall: check j == t.length() before i == s.length(). When both strings end together, t has been spelled: that is 1 way, not 0.
  5. Bottom-up: the same table filled from the bottom-right, dp[i][j] = dp[i+1][j] + (s.charAt(i) == t.charAt(j) ? dp[i+1][j+1] : 0). Each row reads only the row below, so one array of n+1 numbers, updated left to right, is enough.