Java solution using recursion


  • 0
    W

    Start of all possible words is stored using an array of Lists, since we wish to produce all possible valid sentences. Also, a boolean array "valid" is used, which is similar to the word break I problem. Its definition is mentioned in comments in code.

    Main part is generating all combinations of sentences with this data. Recursion is used for the same. The method "fillSentence" does the work of adding the sentences to result.

    begin and end are such that s.substring(begin, end) will be added to the beginning of the resultant sentence "cur". Once, it is added, begin becomes the new end to add next word. For this new end, there will be many start indices of the next word. For all such start indices, we do recursion. When end becomes 0, it means we completed a sentence and it is time to add it to our result; this becomes the returning point of recursion. This recursion could be tricky to understand, so please feel free to ask or discuss regarding the same.

    Further, run time of the first part (to gather data of the start points of words) is O(n^2). I am unsure about the run time of "fillSentence" method. Would appreciate your comments on that. Below is the code :-

    public class Solution {
        
        List<String> result = new ArrayList<String>();
    	String givenString;
    	
        public List<String> wordBreak(String s, Set<String> wordDict) {
    		givenString = s;
    		
    		// valid[i] := true, iff, a valid sentence is possible using characters upto index i (exclusing i). 
    		// So, a sentence is possible if valid[n] = true. n is the length of string s
    		// Base Case: valid[0] = true, since an empty string is a valid sentence
            boolean[] valid = new boolean[s.length() + 1];
            valid[0] = true;
            
            //to store beginning of all valid words forming part of a sentence
            List<Integer>[] start = new ArrayList[s.length() + 1];
            
            // To make initial element as a non-null
            List<Integer> initial = new ArrayList<Integer>();
            initial.add(-1);
            start[0] = initial;
            
            for(int i = 0; i < s.length(); i++) {
                List<Integer> parents = new ArrayList<Integer>();
                for(int j = 0; j <= i; j++) {
                    if(valid[j] && wordDict.contains(s.substring(j, i + 1))) {
                        valid[i+1] = true;
                        parents.add(j);
                    }                
                }
                if(parents.size() == 0)
                    parents.add(-1);
                start[i + 1] = parents;
            }
                         
            
            if(!valid[s.length()])
                return result;
            
            int end = s.length();
            for(int begin : start[end])
            	fillSentence(begin, end, "", start);
                    
            return result;
        }
    	
    	void fillSentence(int begin, int end, String cur, List<Integer>[] start) {
    		if(end == 0) {
    			result.add(cur);
    			return;
    		}
    	
    		if(cur.equals(""))
    			cur = givenString.substring(begin, end);
    		else
    			cur = givenString.substring(begin, end) + " " + cur;
    		
    		end = begin;
    		for(int b : start[end])
    			fillSentence(b, end, cur, start);
    	}
    }

Log in to reply
 

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