139. Word Break

• 139. Word Break
  • Description
  • Solution

Description

Here

Solution

这道题就是dp，从尾巴开始往前扫，砍能否在 dp[start] 能够到达

用tries不足以提高performance，最恶劣的情况就是

final String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
final String[] wordDict = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa" }

这样的情况下，所有情况都要loop才能 return false， 其实早早第一次visit的时候就可以return了

Updated Code is here