华为机试【2、字符串分割】

2、标题:字符串分割
【字符串分割】给定非空字符在s，将该字符串分割成一些子串，使每个子串的ASCIIA码值的和均为水仙花数。
1、若分割不成功则返回 0
2、若分割成功且分割结果不唯一则返回-1
3、若分割成功且分割结果唯一，则返回分割后的子串数目
输入描述: 1、输入字符串的最大长度为 200
输出描述:根据题目描述中情况返回相应的结果
备注:“水仙花数”是指一个三位数，每位上数字的立方和等于该数字本身，如 371是“水仙花数”，因为:371=3^3+7^3+1^3。
示例：
输入
abc
输出
0

def partition_sxhs(s):
    ord_arr = [ord(x) for x in s]

    def is_sxhs(n):
        """判断是否为水仙花数"""
        if n < 100 or n > 999:
            return False
        a = n % 10
        b = (n - a) // 10 % 10
        c = (n - a - b * 10) // 100 % 10
        if n == a ** 3 + b ** 3 + c ** 3:
            return True
        return False

    def backtrack(origin_list, tmp_list, result):
        """回溯算法"""
        if not origin_list:
            result.append(tmp_list[:])
            return
        for i in range(1, len(origin_list) + 1):
            this_list = origin_list[:i]
            # 先截取出来一个水仙花数，再递归数组剩余部分
            if is_sxhs(sum(this_list)):
                tmp_list.append(this_list)
                backtrack(origin_list[i:], tmp_list, result)
                tmp_list.pop()

    tmp_list, result = [], []
    backtrack(ord_arr, tmp_list, result)
    print(result)
    if len(result) == 0:
        return 0
    elif len(result) > 1:
        return -1
    elif len(result) == 1:
        return len(result[0])


print(partition_sxhs("Gddd$Gddd"))