public boolean wordBreak(String s, Set<String> dict) {
		if (s == null || s.length() == 0) {
			return false;
		}

		int maxLength = getMaxLength(dict);

		boolean[] canSegment = new boolean[s.length() + 1];
		canSegment[0] = true;
		for (int i = 1; i <= s.length(); i++) {
			canSegment[i] = false;
			for (int j = 1; j <= maxLength && j <= i; j++) {
				if (!canSegment[i - j]) {
					continue;
				}

				String word = s.substring(i - j, i);
				if (dict.contains(word)) {
					canSegment[i] = true;
					break;
				}
			}
		}
		return canSegment[s.length()];
	}