MY DP solution "Bottom UP"


  • 0
    V

    A lot of people have provided DP solution using recursion. Following is a bottom up solution without using recursion.

    public static boolean wordBreakMyImpl(String s, Set<String> wordDict) {
    		if (s == null || s.length() == 0) {
    			return false;
    		}
    		if (s.length() == 1) {
    			if (wordDict.contains(s)) {
    				return true;
    			} else {
    				return false;
    			}
    		}
    		boolean[] T = new boolean[s.length() + 1];
    		T[0]=true;
    		for (int i = 0; i <= s.length(); i++) {
    			for (int j = 0; j < i ; j++) {
    				if (T[j] == true && wordDict.contains(s.substring(j, i))) {
    					T[i] = true;
    				}
    			}
    		}
    		return T[s.length()];
    
    	}

Log in to reply
 

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