总和字符串编码算法

Question

我正在尝试解决 http://www.geeksforgeeks.org/nutanix-interview-experience-set-1-on-campus-for-internship/的第一个问题。在这个问题中，我们得到了一串十进制数字，我们必须弄清楚是否有办法将其拆分为四个或更多子字符串[">A"，" B"，" C"， ...]，使得A + B = C，B  +  C =  D等。

例如，如果字符串是"12358"，那么答案是true，因为我们可以将其拆分为 ["1"、"2"、" 3"、"5"、"   8"]，其中 1 + 2 = 3、2  + 3 = 5 和 3  +   5 =   8。

类似地，如果字符串是"199100199"，那么答案是true，因为我们可以将其拆分为 ["1"、"99"、" 100"、"  199"]，其中 1 + 99 = 100 和 99 +  100 =  199。  

但是，如果字符串是"2368"，那么答案是false，因为只有方法可以将其分解为四个或更多子字符串 - 即["2"，"3"，"6"，"   8"] - 和3 + 6 ≠ 8。

我可能想到一个使用两个或三个嵌套循环的解决方案，但我认为我需要一个更有效的解决方案？

Answer 1

public static boolean test3(String s, String d1, String d2, int idx1, int idx2) {
if(idx1>=s.length()) return false;
if(idx2>=s.length()) {
d1 = s.substring(0,idx1);
return test3(s,d1,d2,idx1+1,1);
}
if(!d1.isEmpty() && d1.length()+idx2<=s.length()) {
d2 = s.substring(d1.length(),d1.length()+idx2);
int sum = Integer.parseInt(d1) + Integer.parseInt(d2);
String sumStr = Integer.toString(sum);
if(s.substring(d1.length()+d2.length()).startsWith(sumStr)) {
return true;
} else {
return test3(s,d1,d2,idx1,idx2+1);
}
} else {
d1 = s.substring(0,idx1);
return test3(s,d1,d2,idx1+1,idx2);
}
}

我尝试了上述方法，它似乎有效。这是我的解决方案