1096.花括号展开II

链接：1096.花括号展开II
难度：Hard
标签：栈、广度优先搜索、字符串、回溯
简介：给出表示基于给定语法规则的表达式 expression，返回它所表示的所有字符串组成的有序列表。

题解 1 - cpp

• 编辑时间：2023-03-07
• 执行用时：12ms
• 内存消耗：10.9MB
• 编程语言：cpp
• 解法介绍：递归遍历。

class Solution {
public:
    vector<string> braceExpansionII(string expression) {
        if (checkSingal(expression)) expression = expression.substr(1, expression.size() - 2);
        set<string> s;
        vector<string> items = split(expression);
        if (items.size() > 1) {
            for (auto &item : items) {
                for (auto &res : braceExpansionII(item)) {
                    s.insert(res);
                }
            }
        } else {
            string item = items[0];
            vector<vector<string>> res = analysis(item);
            dfs(s, res, 0, "");
        }
        return vector<string>(s.begin(), s.end());
    }
    bool checkSingal(string &expression) {
        if (expression[0] != '{' || expression[expression.size() - 1] != '}') return false;
        int level = 0, i = 0;
        for (; i < expression.size(); i++) {
            if (expression[i] == '{') level++;
            else if (expression[i] == '}') level--;
            if (i != expression.size() - 1 && level == 0) return false;
        }
        return true;
    }
    vector<string> split(string &expression) {
        vector<string> items;
        int level = 0, prev = 0, i = 0;
        for (; i < expression.size(); i++) {
            if (expression[i] == '{') level++;
            else if (expression[i] == '}') level--;
            else if (expression[i] == ',' && level == 0) {
                items.push_back(expression.substr(prev, i - prev));
                prev = i + 1;
            }
        }
        items.push_back(expression.substr(prev, i - prev));
        return items;
    }
    vector<vector<string>> analysis(string &item) {
        vector<vector<string>> res;
        for (int i = 0; i < item.size(); i++) {
            if (item[i] != '{') {
                string s = "";
                s += item[i];
                vector<string> v;
                v.push_back(s);
                res.push_back(v);
            } else {
                int prev = i, level = 0;
                do {
                    if (item[i] == '{') level++;
                    else if (item[i] == '}') level--;
                    if (level != 0) i++;
                } while (level != 0);
                res.push_back(braceExpansionII(item.substr(prev, i - prev + 1)));
            }
        }
        return res;
    }
    void dfs(set<string> &s, vector<vector<string>> &res, int start, string cur) {
        if (start == res.size()) {
            s.insert(cur);
        } else {
            for (int i = 0; i < res[start].size(); i++) {
                dfs(s, res, start + 1, cur + res[start][i]);
            }
        }
    }
};

题解 2 - python

• 编辑时间：2023-03-07
• 执行用时：60ms
• 内存消耗：15.7MB
• 编程语言：python
• 解法介绍：同上。

from sortedcontainers import SortedSet
class Solution:
    def checkSingal(self, expression: str):
        if expression[0] != '{' or expression[-1] != '}':
            return False
        level, i = 0, 0
        while i < len(expression):
            if expression[i] == '{':
                level += 1
            elif expression[i] == '}':
                level -= 1
            if i != len(expression) - 1 and level == 0:
                return False
            i += 1
        return True
    def split(self, expression: str):
        items = []
        level = prev = i = 0
        while i < len(expression):
            if expression[i] == '{':
                level += 1
            elif expression[i] == '}':
                level -= 1
            elif expression[i] == ',' and level == 0:
                items.append(expression[prev:i])
                prev = i + 1
            i += 1
        items.append(expression[prev:])
        return items
    def analysis(self, item: str):
        res = []
        i = 0
        while i < len(item):
            if item[i] != '{':
                res.append([str(item[i])])
            else:
                prev, level = i, 0
                while True:
                    if item[i] == '{':
                        level += 1
                    elif item[i] == '}':
                        level -= 1
                    if level == 0:
                        break
                    else:
                        i += 1
                res.append(self.braceExpansionII(item[prev:i+1]))
            i += 1
        return res
    def dfs(self, s: SortedSet, res: List[List[str]], start: int, cur: str):
        if start == len(res):
            s.add(cur)
        else:
            for i in range(len(res[start])):
                self.dfs(s, res, start+1, cur+res[start][i])
    def braceExpansionII(self, expression: str) -> List[str]:
        s = SortedSet()
        if self.checkSingal(expression):
            expression = expression[1:-1]
        items = self.split(expression)
        if len(items) > 1:
            for item in items:
                for res in self.braceExpansionII(item):
                    s.add(res)
        else:
            item = items[0]
            res = self.analysis(item)
            self.dfs(s, res, 0, '')
        return list(s)

题解 3 - rust

• 编辑时间：2023-03-07
• 执行用时：4ms
• 内存消耗：2.3MB
• 编程语言：rust
• 解法介绍：同上。

use std::collections::BTreeSet;
impl Solution {
    fn check_signal(expression: &Vec<char>) -> bool {
        if *expression.first().unwrap() != '{' || *expression.last().unwrap() != '}' {
            false
        } else {
            let mut level = 0;
            for i in 0..expression.len() {
                if expression[i] == '{' {
                    level += 1
                } else if expression[i] == '}' {
                    level -= 1
                }
                if i != expression.len() - 1 && level == 0 {
                    return false;
                }
            }
            true
        }
    }
    fn split(expression: &Vec<char>) -> Vec<Vec<char>> {
        let mut items: Vec<Vec<char>> = vec![];
        let mut level = 0;
        let mut prev = 0;
        let mut i = 0;
        while i < expression.len() {
            if expression[i] == '{' {
                level += 1;
            } else if expression[i] == '}' {
                level -= 1;
            } else if expression[i] == ',' && level == 0 {
                items.push(
                    expression[prev..i]
                        .iter()
                        .map(|v| *v)
                        .collect::<Vec<char>>(),
                );
                prev = i + 1;
            }
            i += 1;
        }
        items.push(expression[prev..].iter().map(|v| *v).collect::<Vec<char>>());
        items
    }
    fn analysis(item: &Vec<char>) -> Vec<Vec<Vec<char>>> {
        let mut res = vec![];
        let mut i = 0;
        while i < item.len() {
            if item[i] != '{' {
                res.push(vec![vec![item[i]]])
            } else {
                let prev = i;
                let mut level = 0;
                loop {
                    if item[i] == '{' {
                        level += 1;
                    } else if item[i] == '}' {
                        level -= 1;
                    }
                    if level == 0 {
                        break;
                    } else {
                        i += 1;
                    }
                }
                res.push(Solution::_brace_expansion_ii(
                    item[prev..i + 1].iter().map(|v| *v).collect::<Vec<char>>(),
                ))
            }
            i += 1;
        }
        res
    }
    fn dfs(s: &mut BTreeSet<Vec<char>>, res: &Vec<Vec<Vec<char>>>, start: usize, cur: Vec<char>) {
        if start == res.len() {
            s.insert(cur);
        } else {
            for item in res[start].iter() {
                let mut next = cur.clone();
                let mut other = item.clone();
                next.append(&mut other);
                Solution::dfs(s, res, start + 1, next);
            }
        }
    }
    pub fn brace_expansion_ii(expression: String) -> Vec<String> {
        let expression = expression.chars().collect::<Vec<char>>();
        Solution::_brace_expansion_ii(expression)
            .into_iter()
            .map(|v| {
                String::from_utf8(v.into_iter().map(|v| v as u8).collect::<Vec<u8>>()).unwrap()
            })
            .collect()
    }
    fn _brace_expansion_ii(expression: Vec<char>) -> Vec<Vec<char>> {
        let mut expression = expression;
        if Solution::check_signal(&expression) {
            expression.remove(expression.len() - 1);
            expression.remove(0);
        }
        let mut s = BTreeSet::<Vec<char>>::new();
        let items = Solution::split(&expression);
        if items.len() > 1 {
            for item in items {
                for res in Solution::_brace_expansion_ii(item) {
                    s.insert(res);
                }
            }
        } else {
            let res = Solution::analysis(&items[0]);
            Solution::dfs(&mut s, &res, 0, vec![]);
        }
        s.into_iter().collect::<Vec<Vec<char>>>()
    }
}