LEETCODE 1087. Brace Expansion 解题思路分析

题目大意:

我们用一个特殊的字符串 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。