Skip to content

Instantly share code, notes, and snippets.

@bobfang1992

bobfang1992/word_break.java

Last active January 10, 2021 00:42
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save bobfang1992/db05b36e80f5c48fb2e56ac7011c72ba to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save bobfang1992/db05b36e80f5c48fb2e56ac7011c72ba to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. bobfang1992 revised this gist Jan 10, 2021. 1 changed file with 0 additions and 5 deletions.
    5 changes: 0 additions & 5 deletions word_break.java
    View file
    Original file line number Diff line number Diff line change
    @@ -34,8 +34,3 @@ public boolean wordBreak(String s, List<String> wordDict) {
    }
    return dp[s.length()];
    }
    j i substring(i,j) == "pen" dp[6]=true
    j i substring(i j) dp[11] true
    s = "applpenappl e"
    01234567891011
    set = dict = ["apple", "pen"]
  2. bobfang1992 renamed this gist Jan 9, 2021. 1 changed file with 0 additions and 0 deletions.
    0 word_break.py → word_break.java
    View file
    File renamed without changes.
  3. bobfang1992 created this gist Jan 9, 2021.
    41 changes: 41 additions & 0 deletions word_break.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,41 @@
    /*

    s = "applepenapple" dictionary = ["apple", "pen"]
    s = "apple" + "pen" + "apple"
    return True


    s = "appplepearapple" dictionary = ["apple", "pen"]
    return False

    0 <= len(s) <= 10^5
    0 <= len(dictonary) <= 10^5
    */

    // dp[i] should be the result of the this problem for s[0:i]
    // i, j j <= i; dp[j] && set.contains(j, i)

    public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> set = new HashSet<>();
    for (int i = 0; i < wordDict.size(); i++) {
    set.add(wordDict.get(i));
    }

    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;

    for (int i = 1; i < dp.length; i++) {
    for (int j = 0; j <= i; j++) {
    dp[i] = dp[j] && set.contains(s.substring(j, i));
    if (dp[i]) {
    break;
    }
    }
    }
    return dp[s.length()];
    }
    j i substring(i,j) == "pen" dp[6]=true
    j i substring(i j) dp[11] true
    s = "applpenappl e"
    01234567891011
    set = dict = ["apple", "pen"]