给一个字符串,你可以选择在一个字符或两个相邻字符之后拆分字符串,使字符串由仅一个字符或两个字符组成,输出所有可能的结果。

题目链接

样例 1

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

样例 2

输入： "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"]] 

这是我的解法，想问下大家错在哪里：

public class Solution { /* * @param : a string to be split * @return: all possible split string array */ public List<List> splitString(String s) { List<List> result = new ArrayList<>();      dfs(s,0,new ArrayList<String>(),result);     return result;      }   private void dfs(String s, int index, List<String> cur, List<List<String>> result){          if ( index == s.length()){         result.add(new ArrayList<String>(cur));         return;     }          cur.add(String.valueOf(s.charAt(index)));     dfs(s,index+1,cur,result);     cur.remove(cur.size()-1);               if (index < s.length()-1){         cur.add(s.substring(index,index+2));         dfs(s,index+2,cur,result);         cur.remove(cur.size()-1);                 }     } } 

官方解法给个参考：

算法：DFS

由于本题可以选择在一个字符或两个相邻字符之后拆分字符串，且最后需输出所有可能的组合，即每次都需要把整个字符串按照特定要求切分完毕，可以想到利用递归 dfs 来完成；

算法步骤

对字符串进行深度优先搜索，当前位置达到字符串末尾作为边界。搜索时有两种情况：

1. 切割当前的 1 个字符：

• 将这 1 个字符单独作为字符串存入列表
• 当前位置步进 1

1. 切割当前的连续 2 个字符（需满足当前位置不是字符串末尾）：

• 将连续 2 个字符保存为字符串存入列表
• 当前位置步进 2

复杂度分析

• 时间复杂度：O(2^n), n 为字符串长度
  • 除了字符串最后一位，其他位置都有两种切割方式
• 空间复杂度：O(2^n^2),n 为字符串长度
  • 存储所有情况需要所有切分方式*n 的空间

public class Solution {     /*      * @param : a string to be split      * @return: all possible split string array      */     public List<List<String>> splitString(String s) {         List<List<String>> result = new ArrayList<>();         dfs(s, 0, new ArrayList<>(), result);         return result;     }      private void dfs(String s, int index, List<String> current, List<List<String>> result) {         if (index == s.length()) {             result.add(new ArrayList<>(current));             return;         }         // 分割 1 个字符         current.add(String.valueOf(s.charAt(index)));         dfs(s, index + 1, current, result);         current.remove(current.size() - 1);         // 分割 2 个字符         if (index < s.length() - 1) {             current.add(s.substring(index, index + 2));             dfs(s, index + 2, current, result);             current.remove(current.size() - 1);         }     } }