Мой вопрос похож на тот, который задавали о переполнении стека в прошлом http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/
Решение, которое я написал, я не могу понять, поскольку я не использую DP, но все же как получается, что мой sol решает перекрывающиеся проблемы. Я думаю, что это не так. Может кто-нибудь прояснить? мой словарь, который я использую, это {"cat", "catdog", "dog", "mouse"} и тестовая строка как "catdogmouse". Вот метод, который я написал
public static boolean recursiveWordBreak2(String s, int start) {
System.out.println("s is:"+s.substring(start));
if (s.isEmpty() || start >= s.length()) {
return true;
}
for (int i = start; i <= s.length(); i++) {
String str = s.substring(start, i);
System.out.println("substr:" + str);
if (dictSet.contains(str)) {
return recursiveWordBreak2(s, i);
}
}
return false;
}
