My Blog List

[Leetcode Solution] Word break ||

Analysis

  • Because all of the possible solutions are required, a searching function is performed
  • Directly use dfs would lead to exceed time limit
  • Take advantage of the result of word break 1, instead of search from the head of string s, search from the tail of s. 
  • Rather than only using compare substring of s and string in dict, we also check if a state is reachable according to the result of word break dynamic programming. Thus we can guarantee we are always following the searching path that will lead to a possible solution. This is an important pruning strategy.

Note

  • Using depth first search to traversal a searching tree
  • Backtrack a searching solution according to dynamic programming result

Code


UPDATED AT 3RD PASS
at