another attempt on No 30


  • 0
    F

    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)


Log in to reply
 

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