题目大意：
我们用一个特殊的字符串 S 来表示一份单词列表，之所以能展开成为一个列表，是因为这个字符串 S 中存在一个叫做「选项」的概念：
单词中的每个字母可能只有一个选项或存在多个备选项。如果只有一个选项，那么该字母按原样表示。
如果存在多个选项，就会以花括号包裹来表示这些选项（使它们与其他字母分隔开），例如 “{a,b,c}” 表示 [“a”, “b”, “c”]。
例子：”{a,b,c}d{e,f}” 可以表示单词列表 [“ade”, “adf”, “bde”, “bdf”, “cde”, “cdf”]。
请你按字典顺序，返回所有以这种方式形成的单词。
示例 1：
输入："{a,b}c{d,e}f"
输出：["acdf","acef","bcdf","bcef"] 示例 2：
输入："abcd" 输出：["abcd"]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1087
解题思路分析：
这道题我们需要先将字符分组，每个大括号内的字符属于同一组，括号外的字符都各自一组，分组之后，我们使用dfs搜索出所有路径，每条路径上所有字符的连线即是一个单词，dfs遍历完所有路径，也就相应的遍历完所有单词，最后再将单词排序一下即可。
实现代码：
List<String> res=new ArrayList<>(); // 返回结果
public String[] expand(String S) {
// 分组
List<List<Character>> list=new ArrayList<>();
// 先添加一个空的组，作为dfs起点
list.add(new ArrayList<>());
List<Character> current = new ArrayList<>();
boolean isInOption=false;
for(int i=0;i<S.length();i++){
char c = S.charAt(i);
if(c==',') continue;
if(c=='{'||c=='}') {
isInOption = c=='{';
list.add(current);
current=new ArrayList<>();
continue;
}
current.add(c);
if(!isInOption) {
list.add(current);
current=new ArrayList<>();
}
}
// dfs所有路径
dfs(list,0,"");
String[] arr=new String[res.size()];
for(int i=0;i<res.size();i++){
arr[i]=res.get(i);
}
Arrays.sort(arr);
return arr;
}
void dfs(List<List<Character>> list, int index, String s){
if(index==list.size()){
res.add(s);
return;
}
List<Character> charList=list.get(index);
if(charList.size()==0){
dfs(list,index+1,s);
return;
}
for(Character c : list.get(index)){
dfs(list,index+1,s+c);
}
} 本题解法执行时间为3ms。
Runtime: 3 ms, faster than 84.12% of Java online submissions for Brace Expansion.
Memory Usage: 41.7 MB, less than 50.00% of Java online submissions for Brace Expansion.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1087-brace-expansion-解题思路分析/