题目描述:
给定非空字符串s,将该字符串分割成一些子串,使每个子串的ASCII码值的和
均为水仙花数
。
- 若分割不成功,则返回
0
- 若分割成功且分割结果不唯一,则返回
-1
- 若分割成功且分割结果唯一,则返回分割后子串的数目
输入描述:
输入字符串的最大长度为200
输出描述:
根据题目描述中情况,返回相应的结果
补充说明:
“水仙花数”是指一个三位数,每位上数字的立方和等于该数字本身,如371是“水仙花数”,因为:371 = 3^3 + 7^3 + 1^3
示例1
输入:
abc
输出:
0
说明:分割不成功
示例2
输入:
f3@d5a8
输出:
-1
说明:分割成功但分割结果不唯一,可以分割为两组,一组"f3"和"@d5a8",另外一组"f3@d5"和"a8"
示例3
输入:
AXdddF
输出:
2
说明:成功分割且分割结果唯一,可以分割“AX"(153)和"dddF"(370)成两个子串
题解
先截取左边的字符串判断是否是水仙花数,如果左边是,则把右边剩下的字符串作为参数进行递归判断
源码 Java
public class WaterFlower {
static Input input ;
static {
input = new Input("f3@d5a8");
}
static List<List<String>> list = new ArrayList<>();
public static void main(String[] args) {
String string = input.nextLine();
for (int i = 0; i < string.length(); i++) {
String substring = string.substring(0, i);
if (isWaterFlowerNum(substring)) {
List<String> pre = new ArrayList<>();
pre.add(substring);
isOk(string.substring(i), pre);
}
}
if (list.isEmpty()) {
System.out.println(0);
} else if (list.size() > 1) {
System.out.println(-1);
} else {
System.out.println(list.get(0).size());
}
}
public static void isOk(String right, List<String> pre) {
if (right.isEmpty()) {
return;
}
// 如果右边的也是,则说明整个字符串可以被分割
if (isWaterFlowerNum(right)) {
List<String> flist = new ArrayList<>();
flist.addAll(pre);
flist.add(right);
list.add(flist);
}
List<String> nextPre = new ArrayList<>();
nextPre.addAll(pre);
for (int i = 0; i < right.length(); i++) {
String substring = right.substring(0, i);
if (isWaterFlowerNum(substring)) {
isOk(right.substring(i), nextPre);
}
}
}
// 判断是否是水仙花数
public static boolean isWaterFlowerNum(String str) {
if (str == null || str.length() == 0) {
return false;
}
int num = 0;
for (int i = 0; i < str.length(); i++) {
num += str.charAt(i);
}
int old = num;
int sum = 0;
while (num > 0) {
int x = num % 10;
sum = sum + x*x*x;
num /= 10;
}
return sum == old;
}
}