【栈】1096. 花括号展开 II

本文涉及知识点

栈

LeetCode 1096. 花括号展开 II

如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。
花括号展开的表达式可以看作一个由花括号、逗号和小写英文字母组成的字符串，定义下面几条语法规则：
如果只给出单一的元素 x，那么表达式表示的字符串就只有 “x”。R(x) = {x}
例如，表达式 “a” 表示字符串 “a”。
而表达式 “w” 就表示字符串 “w”。
当两个或多个表达式并列，以逗号分隔，我们取这些表达式中元素的并集。R({e_1,e_2,…}) = R(e_1) ∪ R(e_2) ∪ …
例如，表达式 “{a,b,c}” 表示字符串 “a”,“b”,“c”。
而表达式 “{{a,b},{b,c}}” 也可以表示字符串 “a”,“b”,“c”。
要是两个或多个表达式相接，中间没有隔开时，我们从这些表达式中各取一个元素依次连接形成字符串。R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)}
例如，表达式 “{a,b}{c,d}” 表示字符串 “ac”,“ad”,“bc”,“bd”。
表达式之间允许嵌套，单一元素与表达式的连接也是允许的。
例如，表达式 “a{b,c,d}” 表示字符串 “ab”,“ac”,"ad"。
例如，表达式 “a{b,c}{d,e}f{g,h}” 可以表示字符串 “abdfg”, “abdfh”, “abefg”, “abefh”, “acdfg”, “acdfh”, “acefg”, “acefh”。
给出表示基于给定语法规则的表达式 expression，返回它所表示的所有字符串组成的有序列表。

示例 1：
输入：expression = “{a,b}{c,{d,e}}”
输出：[“ac”,“ad”,“ae”,“bc”,“bd”,“be”]
示例 2：
输入：expression = “{{a,z},a{b,c},{ab,z}}”
输出：[“a”,“ab”,“ac”,“z”]
解释：输出中不应出现重复的组合结果。

提示：
1 <= expression.length <= 60
expression[i] 由 ‘{’，‘}’，‘,’ 或小写英文字母组成
给出的表达式 expression 用以表示一组基于题目描述中语法构造的字符串

栈

结果不能有重复元素，且有序，故用set。
运算只有两种：逗号表示+,省略表示乘。
为了方便，我们补上乘号。以下三种情况补上*：
}{
{之前是字母
}之后是字母。

代码

核心代码

class Solution {
public:
	vector<string> braceExpansionII(string expression) {
		string exp;
		exp = expression[0];
		for (int i = 1; i < expression.length(); i++) {
			if ('{' == expression[i]) {
				if (('}' == expression[i - 1]) || isalpha(expression[i - 1])) {
					exp += '*';
				}
			}else if (isalpha(expression[i])) {
				if ('}' == expression[i - 1]) {
					exp += '*';
				}
			}
			exp += expression[i];
		}

		for (int i = 0; i < exp.length(); i++) {
			if ('{' == exp[i]) {
				m_staOpe.emplace('(');
			}else if (',' == exp[i]) {
				m_staOpe.emplace('+');
			}
			else if ('*' == exp[i]) {
				m_staOpe.emplace('*');
			}
			else if ('}' == exp[i]) {
				CalAdd();
			}
			else {
				string strName;
				while (isalnum(exp[i])) {
					strName += exp[i++];
				}
				i--;
				m_staNum.emplace(set<string>{ strName });
				CalMul();
			}
		}
		CalAdd();
		return vector<string>(m_staNum.top().begin(), m_staNum.top().end());
	}
	void CalMul() {
		if (m_staOpe.size() && ('*' == m_staOpe.top())) {
			auto num2 = m_staNum.top();
			m_staNum.pop();
			m_staOpe.pop();
			set<string> ret;
			for (const auto& s1 : m_staNum.top()) {
				for (const auto& s2 : num2) {
					ret.emplace(s1 + s2);
				}
			}
			m_staNum.top().swap(ret);
		}
	}
	void CalAdd() {
		set<string> ret;
		while (m_staOpe.size() && ('(' != m_staOpe.top())) {
			ret.insert(m_staNum.top().begin(), m_staNum.top().end());
			m_staOpe.pop();
			m_staNum.pop();
		}
		m_staNum.top().insert(ret.begin(), ret.end());
		if (m_staOpe.size() && ('(' == m_staOpe.top())) {
			m_staOpe.pop();
		}
		CalMul();
	}
	stack<set<string>> m_staNum;
	stack<char> m_staOpe;
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	string expression;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{
			expression = "{a,b}{c,{d,e}}";
			auto res = Solution().braceExpansionII(expression);
			AssertEx({ "ac","ad","ae","bc","bd","be" },res);
		}
		TEST_METHOD(TestMethod1)
		{
			expression = "{{a,z},a{b,c},{ab,z}}";
			auto res = Solution().braceExpansionII(expression);
			AssertEx({ "a","ab","ac","z" }, res);
		}
	};
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛