LeetCode 1087. Brace Expansion
原题链接在这里:https://leetcode.com/problems/brace-expansion/
题目:
A string S
represents a list of words.
Each letter in the word has 1 or more options. If there is one option, the letter is represented as is. If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}"
represents options ["a", "b", "c"]
.
For example, "{a,b,c}d{e,f}"
represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"]
.
Return all words that can be formed in this manner, in lexicographical order.
Example 1:
Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]
Example 2:
Input: "abcd"
Output: ["abcd"]
Note:
1 <= S.length <= 50
- There are no nested curly brackets.
- All characters inside a pair of consecutive opening and ending curly brackets are different.
题解:
If there is curly braces, all the chars in it could be candidate.
Starting from index 0. Do DFS, DFS state needs orginal string, current index, current StringBuilder and res collection.
If current index i points to '{', then find next index j points to '}', for each of candidate inside brances, append it to StringBuilder and continue DFS at index j+1. After DFS, do backtracking.
If current index i points to char, append it to StringBuilder and continue DFS at index i+1. After DFS, do bracktracking.
When current index points to the end of string, add copy of StringBuilder to res collection.
Time Complexity: exponential.
Space: O(n). n = S.length(). stack space.
AC Java:
class Solution {
public String[] expand(String S) {
if(S == null || S.length() == 0){
return new String[0];
} List<String> res = new ArrayList<String>();
dfs(S, 0, new StringBuilder(), res);
Collections.sort(res);
return res.toArray(new String[0]);
} private void dfs(String s, int i, StringBuilder sb, List<String> res){
if(i >= s.length()){
res.add(sb.toString());
return;
} if(s.charAt(i) == '{'){
int j = i+1;
while(j<s.length() && s.charAt(j)!='}'){
j++;
} String [] candidates = s.substring(i+1, j).split(",");
for(String candidate : candidates){
sb.append(candidate);
dfs(s, j+1, sb, res);
sb.deleteCharAt(sb.length()-1);
}
}else{
sb.append(s.charAt(i));
dfs(s, i+1, sb, res);
sb.deleteCharAt(sb.length()-1);
}
}
}
最新文章
- 致命错误: zlib.h:没有那个文件或目录
- 豪斯课堂K先生全套教程淘宝设计美工第一期+第四期教程(无水印)
- 58同城高性能移动Push推送平台架构演进之路
- android控制系统音量
- SAP程序代码中RANGE表的用法禁忌
- MongoDB安装与启动
- POJ 1564 经典dfs
- 《慕客网:IOS-动画入门》学习笔记
- 锋利的jQuery-7--$.extend()
- linux包之procps之pmap命令
- Hive MapJoin
- c++在函数后面加const
- 让Linux修改IP、DNS等可以更简单
- MongoDB基本shell操作
- JavaScript基础教程1-20160612
- 云计算--网络原理与应用--20171123--网络地址转换NAT
- 我的Python之旅第六天--面向对象初识
- Linux下对lvm逻辑卷分区大小的调整(针对xfs和ext4不同文件系统)
- MySQL设置远程连接
- Redis的appendfsync参数详解