[LeetCode]Pyramid Transition Matrix

这道题首先我们第一反应是考虑BFS或者DFS，但仔细考虑过后BFS事实上是做不了的，比如对于ABC和{ABD, ABE, BCK}，在AB的时候我们有两种选择，而我们BFS只能取一个。所以我们需要用DFS来遍历所有的可能，从最底层开始直到最顶层。对于每个合法的block，我们可以用bit来存，因为只会用到7个字符，比如我们用map[a][c]表示AC后面能够接的字符，每一位代表从a到g的每个字符。时间复杂度O(N^k)，N为最底层的长度，k为所用的字符数量。代码如下：

	class Solution {
	public:
	bool pyramidTransition(string bottom, vector<string>& allowed) {
	int len = bottom.size();
	vector<vector<int>> pyramid(8, vector<int>(8, 0)), map(7, vector<int>(7, 0));
	for (auto& str : allowed)
	map[str[0] - 'A'][str[1] - 'A'] |= 1 << (str[2] - 'A');
	for (int i = 0; i < bottom.size(); ++i)pyramid[len - 1][i] = bottom[i] - 'A';
	return dfs(pyramid, map, len - 1, 0);
	}
	private:
	//N length of current row
	//i index of current column
	bool dfs(vector<vector<int>>& pyramid, vector<vector<int>>& map, int N, int i)
	{
	if (N == 1 && i == 1)return true;
	if (i == N)return dfs(pyramid, map, N - 1, 0);
	int bit = map[pyramid[N][i]][pyramid[N][i + 1]];
	for (int j = 0; j < 7; ++j)
	{
	if (bit & (1 << j))
	{
	pyramid[N - 1][i] = j;
	if (dfs(pyramid, map, N, i + 1))
	return true;
	}
	}
	return false;
	}
	};

view raw Pyramid Transition Matrix.cpp hosted with ❤ by GitHub