Given a set of strings, find the longest string chain. Two strings are chained if
1. both strings belong to the given set
2. the second string is generated by remove one letter in the first string
For example:
Given vector<string> w = {a,ba,bca,bda,bdca}, the longest string chain is bdca->bda->ba->a.
Solution:
Represent the string chain by a Trie like structure. Record the depth while building Trie.
bdca
| |
bda bca
| |
ba ba
|
a
=============
===============
Ref
[1] http://www.1point3acres.com/bbs/thread-131978-1-1.html
1. both strings belong to the given set
2. the second string is generated by remove one letter in the first string
For example:
Given vector<string> w = {a,ba,bca,bda,bdca}, the longest string chain is bdca->bda->ba->a.
Solution:
Represent the string chain by a Trie like structure. Record the depth while building Trie.
bdca
| |
bda bca
| |
ba ba
|
a
=============
===============
Ref
[1] http://www.1point3acres.com/bbs/thread-131978-1-1.html
No comments:
Post a Comment