public int minCut(String s) {
		if(s != null && s.length() > 0) {
			Map<Integer, List<Integer>> map = generateMap(s);
			int[] res = new int[s.length() + 1];
			for(int i = 0; i < s.length(); i++) {
				if(i == 0 || res[i] > 0) {
					for(int length : map.get(i)) {
						if(res[i + length] == 0 || res[i] + 1 < res[i + length]) {
							res[i + length] = res[i] + 1;
						}
					}
				}
			}
			return res[s.length()];
		}
		return 0;
	}