java solution beats 94.18%


  • 0
    C
    public static boolean wordBreak(String s, List<String> wordDict) {
            /**
             *  dp[i] means if the string before i(not the index,it start from 1) th character in s
             *  can break into words.
             */
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < wordDict.size(); j++) {
                    String word = wordDict.get(j);
                    int len = word.length();
                    /**
                     * every time we meet a word in dictionary, we judge if
                     * the string before (i+1-len) can break,if it can not be
                     * break,there is no need to go along,otherwise,then,
                     * we judge if the string between(i+1-len) and i equals
                     * the current word in dictionary
                     *
                     * for example, given s="leetcode" and dictionary ["leet","code"]
                     * we iterate i from 0 to s.length-1,here from 0 to 7
                     * since character before t, the length is no more than
                     * any word in dictionary,so we just ignore,and the dp[1]-dp[3] will
                     * be set to false.when i arrive 3,here it means arrive to the
                     * character 't',we judge dp[i + 1 - len] = dp[3+1-4] = dp[0](this is why we
                     * initially set dp[0] = true),since dp[0] = true,we come to substring string
                     * between (i + 1 -len) and i ,since substring method does not include the end,
                     * we substring from(i+1-len,i+1) here s.substring(0,4) = "leet",it equals
                     * the first string in dictionary.so we find it and break the inner loop,
                     * so we set dp[i+1] = dp[3+1] = dp[4] = true, it means string before the 4th
                     * character (inclusive)in s can break into words.
                     */
                    if (len <= (i+1) && dp[i+1-len]) {
                        if (s.substring(i + 1 - len,i + 1).equals(word)) {
                            dp[i + 1] = true;
                            break;
                        }
                    }
                }
            }
            return dp[s.length()];
        }
    

Log in to reply
 

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