My Java Solution


  • 0
    S

    Here I have my Java solution, which uses recursion.


  • 0
    S

    This is basically the same as the permutation problem, where each character gets permuted. Here the difference is use of word instead of character. Also, the judging system complains about taking too long for empty output, I added a small validity check to see if all character is in the dict.

    Here is my code:

    public class Solution {
        ArrayList<String> output;
        StringBuilder sb;
        public ArrayList<String> wordBreak(String s, Set<String> dict) {
            output = new ArrayList<String>();
            sb = new StringBuilder();
            if (s.length() == 0 || dict.size() == 0) {
                return output;
            }
            // to speed up, check if each character is in the dict
            boolean found = false;
            for (int i = 0; i < s.length(); i++) {
                for (String dictWord : dict) {
                    if (dictWord.indexOf(s.charAt(i)) >= 0) {
                        found = true;
                        break;
                    }
                    found = false;
                }
                if (!found) return output;
            }
            
            findWords(s, dict);
            return output;
        }
        public void findWords(String s, Set<String> dict) {
            // base case: return when string is ""
            if (s.length() == 0) {
                output.add(sb.toString());
                return;            
            }
            // check substring from 0 to i
            for (int i = 1; i <= s.length(); i++) {
                String toFind = s.substring(0, i);
                if (dict.contains(toFind)) {
                    if (sb.length() > 0)
                        sb.append(" ");
                    sb.append(toFind);
                    findWords(s.substring(i), dict);
                    int start = sb.lastIndexOf(toFind);
                    if (start > 0) start = start - 1;
                    int end = sb.length();
                    sb.delete(start, end);
                }
            }
            return;
        }
    }

Log in to reply
 

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