https://leetcode.com/contest/weekly-contest-137/problems/longest-string-chain/
N個の文字列がある。
文字列Aのどこかにちょうど1文字加えることで文字列Bになる → AはBのpredecessorと言う。
N個の文字列から何個か取って並べるとする。
それが、S1, S2, ..., SNであるとすると、S1はS2のpredecessor, S2はS3のpredecessor, ...という感じに
全てpredecessorの関係になっている列の最長は?
1 ≦ N ≦ 1000
1 ≦ 文字列長 ≦ 16
前提知識
解説
https://leetcode.com/contest/weekly-contest-137/submissions/detail/229839298/
今回の問題は有向グラフに帰着することができる。
ある文字列Aがある文字列Bのpredessorであるとき、A -> Bと辺を張ることにする。
こうすると、できあがる有向グラフはDAGの形になっている。
DAGで最長パスを求めるときは、トポロジカルソートをしてDPという相場が決まっているのでやる。
dp[cu] := パスの末尾が頂点cuであるパスの最長
class Solution { public: int longestStrChain(vector<string>& A) { int n = A.size(); TopologicalSort ts(n); rep(a, 0, n) rep(b, 0, n) if (A[a].size() + 1 == A[b].size()) { int aa = 0; rep(bb, 0, A[b].size()) { if (aa == A[a].size()) break; if (A[a][aa] == A[b][bb]) aa++; } if (aa == A[a].size()) ts.add_edge(a, b); } vector<int> ord; ts.sort(ord); vector<int> dp(n, 1); fore(cu, ord) fore(to, ts.E[cu]) chmax(dp[to], dp[cu] + 1); int ans = 0; rep(i, 0, n) chmax(ans, dp[i]); return ans; } };