Solution Using just array


  • 2
    I
    import java.util.Set;
    
    public class Solution {
        public boolean wordBreak(String s, Set<String> dict) {
                //a[] sotre the index for the subString from which to s.length can be breaked.
               //
        	int a[] = new int[s.length() + 1];
        	int j = 0;
        	a[0] = s.length();
        	for(int i= s.length() - 1; i >= 0; i--){
        		for(int k = j; k>=0; k--){
        			if(dict.contains(s.substring(i, a[k]))){
        				a[++j] = i;
        				break;
        			}
        		}
        	}
            
            return a[j]==0;
        }
    }

Log in to reply
 

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