Recursive Solution (Java)


  • 0
    Q
    public class WordBreak {
    	private Map<String, Boolean> mem = new HashMap<String, Boolean>();
    	public boolean wordBreak(String s, Set<String> wordDict) {
    		if (wordDict.contains(s) ||  Boolean.TRUE==mem.get(s)) {
    			return true;
    		}
            else if (mem.containsKey(s)){
    		    return false;
    		}
    		Iterator<String> iter = wordDict.iterator();
    		while (iter.hasNext()) {
    			String strt = iter.next();
    			if (s.startsWith(strt)) {
    				String sk = s.substring(strt.length());
    				if (mem.containsKey(sk)) {
    					if (mem.get(sk)) {
    						return true;
    					}
    					continue;
    				} else if (wordBreak(sk, wordDict)) {
    					mem.put(sk, true);
    					return true;
    				}
    				mem.put(sk, false);
    			}
    		}
    		return false;
    	}
    }

  • 0
    Q

    Another one

    public class Solution {
       Map<String, Boolean> mem = new HashMap<String, Boolean>();
       public boolean wordBreak(String s, Set<String> wordDict) {
            if (wordDict.contains(s) || Boolean.TRUE==mem.get(s)){
                return true;
            }
            else if (mem.containsKey(s)){
                return false;
            }
    		for (int i = 1; i < s.length(); i++) {
    			String s1 = s.substring(0, i);
    			String s2 = s.substring(i);
    
    			Boolean b1 = mem.get(s1);
    			if (b1 == null){
    				b1 = wordBreak(s1, wordDict);
    				mem.put(s1, b1);
    			}
    			if (b1){
    			    Boolean b2 = mem.get(s2);
    				if (b2 == null){
    					b2 = wordBreak(s2, wordDict);
    					mem.put(s2, b2);
    				}
    				if (b2){
        				return true;
        			}
    			}
    		}
    		return false;
    	}
    }

Log in to reply
 

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