2ms Java solution, DP. Bonus ugly streams solution :)


  • 2
    A

    Counting the max string length in the dictionary and terminating the inner loop early speeds it up from 9ms to 2ms.

    public boolean wordBreak(String s, Set<String> wordDict) {
        int[] mem = new int[s.length()+1];
        mem[0] = 1;
        int max = 0;
        for (String word: wordDict) 
            max = Math.max(max,word.length());
        for (int i = 0; i < s.length(); i++) 
            if (mem[i] == 1) 
                for (int j = i; j < mem.length && j - i <= max; j++) 
                    if (wordDict.contains(s.substring(i,j))) 
                        mem[j] = 1;
        return mem[s.length()] == 1;
    }
    

    Ugly bonus:

    public boolean wordBreak(String s, Set<String> wordDict) {
        if (wordDict.size() == 0) return false;
        short[] mem = new short[s.length()+1];
        mem[0] = 1;
        IntStream.range(0, s.length())
            .forEach(i -> { 
                if (mem[i] == 1)  
                    IntStream.range(i, s.length() + 1)
                        .filter(j -> wordDict.contains(s.substring(i,j)))
                        .forEach(j -> mem[j] = 1);
        });
        return mem[s.length()] == 1;
    }

  • 0
    T

    int max is not used in the streams version...


  • 0
    T
    This post is deleted!

  • 1
    T

    Two premature? optimizations for the inner loop:

    1. Simplify loop condition, calculate range only once (it hurts readability a bit):

      for (int j = Math.min(i + max, s.length()); j > i; --j)
      
    2. Skip processing if we already have a solution: we may find an alternative at best, so we can save a substring (linear time) and a contains (amortized constant or log time [don't know if it's a HashSet we receive]).

      if (mem[j] == 1) continue;
      

    Neither decreased the 2ms runtime though, but I think it's because the inputs are too small.


  • 0
    A

    Thanks for noticing. Removed.


  • 0
    A
    1. Yes, this does indeed save one comparison per loop cycle.
    2. I tried this before and, since it didn't improve the runtime, decided to remove it to keep the code shorter and avoid, as you said, premature optimizing if's.
      Thanks for both good comments.

  • 0
    T

    Just one more little thing: you start at j = i which means s.substring(i,i).equals(""). We already know that mem[j] == mem[i] == 1 so checking is superfluous like in 2., therefore starting at j = i + 1 is equivalent.


  • 0
    A

    Ahaha, this is next level nit-picking ! :D Thanks! Great comments on code quality :)


Log in to reply
 

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