大厂面试真题详解：分割字符串
给一个字符串,你可以选择在一个字符或两个相邻字符之后拆分字符串,使字符串由仅一个字符或两个字符组成,输出所有可能的结果
样例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来完成;
算法步骤
对字符串进行深度优先搜索，当前位置达到字符串末尾作为边界。搜索时有两种情况：
切割当前的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); } } } - 发表于:
- 原文链接：http://news.51cto.com/art/202011/630748.htm
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
