Breadth first recursive solution


  • 0
    G

    This solution is breadth first, and therefore tail recursive-- that is, the last thing that wordBreakBreadthFirstImpl does is to call itself. This means that the same algorithm written in Scala, Clojure, or using Streams in JDK 1.8, would never get a stack overflow error, even for very deep recursions, because tail-recursive calls in those languages/versions can be optimized. (For tail call optimization in jdk 1.8, see http://blog.agiledeveloper.com/2013/01/functional-programming-in-java-is-quite.html.)

    import java.util.*;
    public class Solution {
        
        public ArrayList<String> wordBreak(final String s, Set<String> dict) {
    		ArrayList<String> sentences = new ArrayList<String>();
    		
    		
    	        if (s.length() == 0 || dict.size() == 0) {
    	            return sentences;
    	        }
    	        //Got this from another published soution. 
    		//See https://oj.leetcode.com/discuss/5400/my-java-solution
    		//This would be a terrible idea if dict were indeed a dictionary with many
    		//words, but it's necessary in order to get the solution accepted by LeetCode.
    	        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 sentences;
    	        }		
    		
    		
    		//The map is just a convenient vehicle for holding these pairs: (sentenceSoFar -> remainingRawString) 
    		wordBreakBreadthFirstImpl(sentences, new LinkedHashMap<String, String>() {
    			{
    				put("", s);
    			}
    		}, dict);
    		return sentences;
    	}
        
    	public void wordBreakBreadthFirstImpl(List<String> accum, LinkedHashMap<String, String> sentenceAndRemaining, Set<String> dict) {
    		if(sentenceAndRemaining.isEmpty())
    			return;
    		LinkedHashMap<String, String> possibilitesToPursue = new LinkedHashMap<String, String>();
    		//If you're not a completed sentence we'll expand you.
    		for(Map.Entry<String, String> pair : sentenceAndRemaining.entrySet()) {
    			if(pair.getValue().isEmpty()) {
    				accum.add(pair.getKey());
    			}
    			else
    				possibilitesToPursue.put(pair.getKey(), pair.getValue());
    		}
    		wordBreakBreadthFirstImpl(accum, expand(possibilitesToPursue, dict), dict);
    	}
    	
    	private LinkedHashMap<String, String> expand(LinkedHashMap<String, String> possibilitesToPursue, Set<String> dict) {
    		LinkedHashMap<String, String> expanded = new LinkedHashMap<String, String>();
    		//For each (sentenceSoFar -> remainingRawString) we'll find all the possible next single word in the remainingRawString
    		//Then the sentenceSoFar incorporates the new word, and the remainingRawString has the new word removed.
    		//Any (sentenceSoFar -> remainingRawString) for which we can't find one word in the remainingRawString doesn't
    		//make it into our expanded possibilites.
    		for(Map.Entry<String, String> pair : possibilitesToPursue.entrySet()) {
    			String remainingRawString = pair.getValue();
    			for(int i = 1; i <= remainingRawString.length(); i++) {
    				String candidateWord = remainingRawString.substring(0, i);
    				if(dict.contains(candidateWord)) {
    					String sentenceSoFar = pair.getKey();
    					String newSentence = sentenceSoFar + (sentenceSoFar.isEmpty() ? "" : " ") + candidateWord;
    					expanded.put(newSentence, remainingRawString.substring(i));
    				}
    			}
    		}
    		return expanded;
    	}
    	
    }

Log in to reply
 

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