Java recursive solution


  • 0
    J

    idea is simple, characters between "start" and "end" is valid word, and characters between "end" and the end of string can be broken into words.

    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.isEmpty()) return false;
        HashSet<String> words = new HashSet<>(wordDict);
        int[] breakable = new int[s.length()];
        return wordBreak(s, 0, 1, words, breakable);
      }
    
      private boolean wordBreak(String s, int start, int end, HashSet<String> words, int[] breakable) {
        if (breakable[start] !=0 ) return breakable[start] > 0;
        for (; start < end && end <= s.length(); end++) {
          String candidate = s.substring(start, end);
          if (words.contains(candidate)) {
            if (end >= s.length() || wordBreak(s, end, end + 1, words, breakable)) {
              breakable[start] = 1;
              return true;
            }
          }
        }
        breakable[start] = -1;
        return false;
      }
    

Log in to reply
 

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