Two different strategies about DP get different results


  • 29
    C

    firstly I used DP from head of the string to traverse the dp-map: and then got a “Time Limit Exceeded” Error with the unpassed case "aaaaaaaaa....ab", but this method can pass such case like "baaaaaa....a"

    secondly I found the answer on internet with the dp-strategy, and saw the dp-method from tail of the string to traverse the dp-map, then got an "Accepted" ,but i tested the case like "baaaaaa....a" on my own computer ,finally the result is “Time Limit Exceeded”

    above all, i think the two strategies are the same ; and the OJ's test cases may have some infulence on different methods!


  • 0
    K

    I too observed this behavior in this problem


  • 0
    S

    exactly and so far I've not yet come up with a solution which would pass both test cases. Anyone has any idea?


  • 5
    Y

    I first used the DP algorithm which is acceptable to the last question (Word Break) to check if the string is word breakable, then recursively explored the possible answers (I don't think it's a DP algorithm) if yes. This method can pass all test cases here and also handle your "baaaaaaaaaaaaaaaaaa...a" case.


  • 1

    Thanks so much for pointing this out. I have added the test case so both mentioned solutions get Time Limit Exceeded now. Thanks!


Log in to reply
 

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