LintCode 680 Split String

思路

dfs搜索问题，可以使用subset的模板，只是dfs中for循环条件有所改变，因为可以接受连续的最多2个字符作为子串。
时间复杂度O(2^n)
空间复杂度O(logn)

代码

public class Solution {
    /** @param : a string to be split* @return: all possible split string array*/public List<List<String>> splitString(String s) {
    // write your code hereList<List<String>> results = new ArrayList<>();if (s == null) {
    return results;}dfs(s, 0, new ArrayList<>(), results);return results;}private void dfs(String s,int startIndex,List<String> local,List<List<String>> results) {
    if (startIndex == s.length()) {
    results.add(new ArrayList<>(local));return;}for (int i = startIndex; i < s.length(); i++) {
    // 此处也可以加在for循环条件里：i < startIndex + 2 && i < s.length()if (i >= startIndex + 2) {
    break;}String sub = s.substring(startIndex, i + 1);local.add(sub);dfs(s, i + 1, local, results);local.remove(local.size() - 1);}}
}