Why is the forward DP slower than the Top Solution's DP?


  • 0
    A

    My solution: 20ms, where as the Top Solution's DP is 15ms

    This is similar idea to Top Solution's, but does a forward scan instead. I thought the logic is more straight forward this way. It actually runs fewer inner iterations, but somehow is still slower?

    Anyone can help pointing out where is the slow down?

    public boolean wordBreak(String s, List<String> dict) {
            Set<String> wordDict = new HashSet<>();
            // Make Set
            for (String word : dict) {
                wordDict.add(word);
            }
            
            boolean[] breakable = new boolean[s.length()+1];
            breakable[0] = true;
            
            for (int i = 0; i <= s.length(); i++) {
                if (breakable[i]) {
                    // Scan rest of string, find all possible words starting from prev token
                    for (int j = i+1; j <= s.length(); j++) {
                        boolean isWord = wordDict.contains(s.substring(i, j));
    
                        if (isWord && j == s.length()) {
                            return true;
    
                        } else if (isWord) {
                            breakable[j] = true;
                        }
                    }
                }
            }
            return breakable[s.length()];
        }
    

    Top solution's

        public boolean wordBreak(String s, List<String> dict) {
            Set<String> wordDict = new HashSet<>();
            // Make Set
            for (String word : dict) {
                wordDict.add(word);
            }
            
            boolean [] breakable = new boolean[s.length()+1];
            breakable[0] = true;
    
            for(int i=1;i<=s.length();i++){
                for(int j=0;j<i;j++){
                    if(breakable[j]&&dict.contains(s.substring(j,i))){        // Weird reversed indexing??
                        breakable[i] = true;
                        break;
                    }
                }
            }
            return breakable[s.length()];
        }
    

Log in to reply
 

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