样例

输入： "123"

输出： [["1","2","3"],["12","3"],["1","23"]]

输入： "12345"

输出： [["1","23","45"],["12","3","45"],["12","34","5"],["1","2","3","45"],["1","2","34","5"],["1","23","4","5"],["12","3","4","5"],["1","2","3","4","5"]]

class Solution:

    """

    @param: : a string to be split

    @return: all possible split string array

    """

    result = []

    def splitString(self, s):

        # write your code here

        self.split_string_helper(s, start_index=0, path=[])

        return self.result

    def split_string_helper(self, s, start_index, path):

        if start_index >= len(s):

            self.result.append(list(path))

            return

        for step in (1, 2):

            if start_index + step > len(s): # if no this clause, bug for "1" => ["1", "1"]

                return

            comb = s[start_index:start_index+step]

            path.append(comb)

            self.split_string_helper(s, start_index+step, path)

            path.pop()

样例

输入："lintcode"，["de","ding","co","code","lint"]

输出：["lint code", "lint co de"]

解释：

插入一个空格是"lint code"，插入两个空格是 "lint co de"

输入："a"，[]

输出：[]

解释：字典为空

import sys

import json

def load_data():

    data = json.loads(sys.stdin.read())

    return data["string"], set(data["word_list"])

def dfs(s, start, words, arr, results):

    if start == len(s):

        results.append(",".join(arr))

        return

    for i in range(start, len(s)):

        word = s[start:i+1]

        if word in words:

            arr.append(word)

            dfs(s, i+1, words, arr, results)

            arr.pop()

def main():

    string, words = load_data()

    results, arr = [], []

    start = 0

    dfs(string, start, words, arr, results)

    results.sort()

    print(json.dumps({'results': results}))

if __name__ == "__main__":

    main()

class Solution:

    """

    @param: s: A string

    @param: wordDict: A set of words.

    @return: All possible sentences.

    """

    def wordBreak(self, s, wordDict):

        # write your code here

        self.cache = {}

        return [" ".join(words) for words in self.dfs(s, words_dict=wordDict)]

    def dfs(self, s, words_dict):

        if s in self.cache:

            return self.cache[s]

        if not s:

            return [[]]

        result = []

        for i in range(0, len(s)):

            word = s[:i + 1]

            if word in words_dict:

                for w in self.dfs(s[i + 1:], words_dict):

                    result.append([word] + w)

        self.cache[s] = result

        return result