Longest String Chain [LeetCode 1048]

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;
	}
};