10ms Simple Java DP Solution


  • 0
    M
        public boolean wordBreak(String s, List<String> wordDict) {
            if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) return false;
            int n = s.length();
            Set<String> dic = new HashSet<>(wordDict);
            boolean[] p = new boolean[n + 1];
            p[0] = true;
            for (int i = 1; i <= n; ++i) {
                for (int j = i; j >= 1; --j) {
                    p[i] = p[j - 1] && dic.contains(s.substring(j - 1, i));
                    if (p[i]) break;
                }
            }
            return p[n];
        }
    

Log in to reply
 

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