Java DP Bottom-up 20 line solution with pruning. 3ms, beats 92%


  • 4
    H

    We store the max and min string lengths from the wordDict to only observe the indexes we are interested in. Feel free to ask any questions or further optimize.

    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            int n = s.length();
            boolean[] canWordBreak = new boolean[n + 1];
            int minLength = Integer.MAX_VALUE;
            int maxLength = Integer.MIN_VALUE;
            for(String str : wordDict) {
                minLength = Math.min(minLength, str.length());
                maxLength = Math.max(maxLength, str.length());
            }
            canWordBreak[0] = true;
            for(int i = minLength; i <= n; i++) {
                for(int j = i - minLength; j >= 0 && j >= i - maxLength; j--) {
                    if(canWordBreak[j] && wordDict.contains(s.substring(j, i))) {
                        canWordBreak[i] = true;
                        break;
                    }
                }
            }
            return canWordBreak[n];
        }
    }

  • 1
    X

    Really smart pruning. Thank for sharing. I use your idea and code by myself, surprisingly beats 93.48.


  • 1
    Y

    Brilliant, but should not use "break"


Log in to reply
 

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