Tuesday, March 22, 2016

MJ [56] Longest String Chain

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

No comments:

Post a Comment