# another attempt on No 30

• eg. : s: "barfoothefoobarman"
dict: ["foo", "bar"]
the return is [0,9].

since barfoo is a Combination of all the words in the Dict and foobar is another combination

the first "barfoo" starts from index 0
the second "foobar" starts from index 1

first of all, the combination is unrelated to the sort of words. it is a combination problem, so the Time Complexity is O(exp(n)), it doesnt work

now the 1st attempt is convert this problem to a Tree Problem

for example:

``````         bar
foo    the
foo    bar man
``````

this is a binary Tree, and very soon we found it is sort of a problem to find all the path connected each tree nodes.
since pre-order in-order and post-order is a combination of nodes subset

eg: ["foo","bar","tes"]

in a binary tree it is:

``````            foo
bar   tes
``````

pre-order is [foo bar tes]
in-order is [bar foo tes]
post-order is [tes bar foo]

then they are the 3 of all combinations of those 3 words:
foobartes tesbarfoo barfootes，

actually P(3) = 3! = 3 * 2 * 1 = 6 it should be 6 not 3
those [tesfoobar bartesfoo 和 footesbar] are missed

then it is also a wrong solution actually Tree could turn into Graph

s: "barfoothefoobarman"

then as a dict [foo, bar, tes] it is a full connected graph of 3 vex [foo，bar, tes]

with the presentation of adjacent table
foo [bar, test]
bar [foo, test]
test [foo, bar]

actually as s:"barfoothefoobarman" this sequence is a single order connected graph

``````  bar [foo]
foo [the]
the [foo]
foo [bar]
bar [man]

then, we found that , this problem is turned into a graph problem, find some sub-node they isolated others which are words in the dicts. but these words are uni-direction not vice verse
``````

OK, then this Problem's solution is found those isolated, and try to find their startIndex and endIndex, this Ops time complexity is O(n)

then， the whole s is converted to barfoothefoobarman
then the first sequence is [the -> (6, 9), man -> (15, 19)]

and just try to find each next Words' StartIndex and Prev Words' EndIndex，and give the measurement on if the length of difference on those indexes is mode by length of all the words in the dict.

in this example, dict [foo, bar] 's word;s length is 6
foo + bar = 3 * 2 = 6 (l = sizeOfDict * n)

the 1st StartIndex = 6 the 1st possible sequence is 6 - 0 = 6, 6 == 6 * 1 and it is
l * 1

the 2nd StartIndex = 16 and the 2nd possible sequence is 15 - 9 = 6, 6 == 6 * 1 is also l * 1

and now we found that it converts a combination problem into a solution to search pattern by length. and reduced the Time Complexity to O(n)

and the result is (0,9)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.