public boolean wordBreak(String s, Set<String> dict) {
		if (s == null || dict.size() == 0)
			return false;
		boolean dp[] = new boolean[s.length() + 1];
		
		
		dp[0]=true;
		
		for(int i=1;i<=s.length();i++){
			for(int k=0;k<i;k++){
				if(dp[k]&&dict.contains(s.substring(k, i)))
					dp[i]=true;
			}
		}

		for(int i=1;i<=s.length();i++)
			System.out.print(i+"-"+dp[i]);
		System.out.println();
		return dp[s.length()];
	}