深搜系列之分割字符串

数据结构深度优先搜索
dfs系列, 数据结构, 高频面试题总结

题目详情

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

样例：
给一个字符串”123”
返回[[“1”,”2”,”3”],[“12”,”3”],[“1”,”23”]]

思路：

  • 深度优先搜索 + 回溯
  • for循环里面控制是一个字符还是两个字符

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 here
        List<List<String>> results = new ArrayList<>();
        if (s == null) {
            return results;
        } else if (s.length() == 0) {
            results.add(new ArrayList<>());
            return results;
        }
        
        dfsHelper(results, new ArrayList<>(), 0, s);
        return results;
    }
    
    private void dfsHelper(List<List<String>> results,
                           List<String> result,
                           int index,
                           String s) {
        if (index == s.length()) {
            results.add(new ArrayList<>(result));
            return;
        }                       
        
        for (int i = index; i < index + 2 && i < s.length(); i++) {
            String substring = s.substring(index, i+1);
            result.add(substring);
            dfsHelper(results, result, i+1, s);
            result.remove(result.size() - 1);
        }
                               
    }
}
Compartir Comentarios