本文解决一个有趣的字符串分割问题：将给定字符串分割成若干子串，使得每个子串的ASCII码值之和均为水仙花数（三位自幂数），并根据分割结果的唯一性返回相应的状态码。
题目描述
给定非空字符串 s，将其分割成一些子串，使每个子串的ASCII码值的和均为水仙花数。
返回规则：
- 若分割不成功则返回
0 - 若分割成功且分割结果不唯一则返回
-1 - 若分割成功且分割结果唯一，则返回分割后的子串数目
备注： "水仙花数"是指一个三位数，每位上数字的立方和等于该数字本身。三位水仙花数有：153、370、371、407。
输入输出要求
输入： 字符串的最大长度为 200
输出： 返回相应的结果（0、-1 或正整数）
示例
示例1
输入： abc
输出： 0
说明： 分割不成功（'a'=97, 'b'=98, 'c'=99，无法组合成水仙花数）
示例2
输入： f3@d5a8
输出： -1
说明： 分割成功但结果不唯一
- 方案1：
"f3"(153) 和"@d5a8"(370) - 方案2：
"f3@d5"(370) 和"a8"(153)
示例3
输入： AXdddF
输出： 2
说明： 分割成功且结果唯一
"AX"(65+88=153) 和"dddF"(100×3+70=370)
优化后的Java解法
import java.util.*;
public class NarcissisticSubstring {
// 预计算所有三位水仙花数
private static final Set<Integer> NARCISSISTIC_NUMBERS = Set.of(153, 370, 371, 407);
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
// 输入验证
if (s == null || s.isEmpty() || s.length() > 200) {
System.out.println(0);
return;
}
List<List<String>> allSolutions = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), allSolutions);
// 根据解的数量返回结果
if (allSolutions.isEmpty()) {
System.out.println(0);
} else if (allSolutions.size() > 1) {
System.out.println(-1);
} else {
System.out.println(allSolutions.get(0).size());
}
}
/**
* 回溯算法寻找所有有效的分割方案
*/
private static void backtrack(String s, int start, List<String> current, List<List<String>> solutions) {
// 剪枝：如果已经找到超过1个解，可以提前终止（因为只需要知道是否唯一）
if (solutions.size() > 1) {
return;
}
// 基础情况：整个字符串已处理完毕
if (start == s.length()) {
solutions.add(new ArrayList<>(current));
return;
}
int sum = 0;
// 尝试从当前位置开始的所有可能子串
for (int end = start; end < s.length(); end++) {
sum += s.charAt(end);
// 如果当前和已经超过最大水仙花数，后续只会更大，可以剪枝
if (sum > 407) {
break;
}
// 如果当前和是水仙花数，尝试以此作为分割点
if (NARCISSISTIC_NUMBERS.contains(sum)) {
current.add(s.substring(start, end + 1));
backtrack(s, end + 1, current, solutions);
current.remove(current.size() - 1); // 回溯
// 提前终止优化
if (solutions.size() > 1) {
return;
}
}
}
}
}
算法优化亮点
- 预计算水仙花数：使用
Set存储已知的四个三位水仙花数，避免重复计算 - 剪枝优化：
- 当和超过407（最大水仙花数）时提前终止内层循环
- 当找到超过1个解时提前终止整个搜索
- 内存效率：使用回溯而非字符串拼接，减少内存分配
- 代码清晰：分离关注点，主函数处理输入输出，回溯函数专注搜索逻辑
- 边界处理：正确处理空输入和超长输入的情况
时间复杂度分析
- 最坏情况：O(2^n)，其中 n 是字符串长度（每个位置都可能是分割点）
- 实际表现：由于水仙花数的稀疏性和剪枝优化，实际运行时间远低于理论最坏情况