給一個字符串,你可以選擇在一個字符或兩個相鄰字符之后拆分字符串,使字符串由僅一個字符或兩個字符組成,輸出所有可能的結(jié)果

樣例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"]] 

算法：DFS

由于本題可以選擇在一個字符或兩個相鄰字符之后拆分字符串，且最后需輸出所有可能的組合，即每次都需要把整個字符串按照特定要求切分完畢，可以想到利用遞歸dfs來完成;

算法步驟

對字符串進行深度優(yōu)先搜索，當前位置達到字符串末尾作為邊界。搜索時有兩種情況：

切割當前的1個字符：

• 將這1個字符單獨作為字符串存入列表
• 當前位置步進1

切割當前的連續(xù)2個字符(需滿足當前位置不是字符串末尾)：

• 將連續(xù)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); 
        } 
    } 
}