The test cases of "aaaaa...b" and "baaaa...a" combined with the time limitation criteria is questionable. I believe most people saw time limit hit on their first try. I was using DP which is supposed to be very efficient but unfortunately hit the time limit.
It's actually very simple to work around the 2 extreme test cases: just call the Word Break I function to filter out the error cases, then call my DP function for Word Break II again (which previously failed because of time limit). Calling 2 functions is much desired than calling only 1 in this case, but I don't think this represents the typical use case in the real world.