LeetCode 756. 金字塔转换矩阵

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 756. 金字塔转换矩阵原题链接中等

作者：

wzc1995 , 2019-10-15 07:21:08 , 所有人可见 , 阅读 1004

4

1

题目描述

现在，我们用一些方块来堆砌一个金字塔。每个方块用仅包含一个字母的字符串表示。

使用三元组表示金字塔的堆砌规则如下：

(A, B, C) 表示，C 为顶层方块，方块 A、B 分别作为方块 C 下一层的的左、右子块。当且仅当 (A, B, C) 是被允许的三元组，我们才可以将其堆砌上。

初始时，给定金字塔的基层 bottom，用一个字符串表示。一个允许的三元组列表 allowed，每个三元组用一个长度为 3 的字符串表示。

如果可以由基层一直堆到塔尖返回 true，否则返回 false。

样例

输入：bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
输出：true
解释：
可以堆砌成这样的金字塔:
    A
   / \
  G   E
 / \ / \
B   C   D

因为符合 BCG、CDE 和 GEA 三种规则。

输入：bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
输出：false
解释：
无法一直堆到塔尖。
注意, 允许存在像 ABC 和 ABD 这样的三元组，其中 C != D。

提示

bottom 的长度范围在 [2, 8]。
allowed 的长度范围在 [0, 200]。
方块的标记字母范围为 {'A', 'B', 'C', 'D', 'E', 'F', 'G'}。

算法

(暴力枚举，哈希表)

从最底层开始，暴力拓展出所有可能的上一层的字符串，并逐一递归判断这些字符串的可行性。
判断过程中，可以通过哈希表进行加速。

C++ 代码

class Solution {
private:
    unordered_set<char> h[7][7];
    unordered_set<string> seen;

    vector<string> make_candidates(const string &s) {
        const int n = s.size();

        vector<string> candidates;
        candidates.push_back("");

        for (int i = 0; i < n - 1; i++) {
            vector<string> new_candidates;
            for (const string &cand : candidates)
                for (char c : h[s[i] - 'A'][s[i + 1] - 'A'])
                    new_candidates.push_back(cand + c);

            candidates = new_candidates;
        }

        return candidates;
    }

    bool solve(const string &s) {
        if (s.size() == 1)
            return true;

        if (seen.find(s) != seen.end())
            return false;

        seen.insert(s);

        vector<string> candidates = make_candidates(s);
        for (const string &cand : candidates)
            if (solve(cand))
                return true;

        return false;
    }

public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for (const auto &p : allowed)
            h[p[0] - 'A'][p[1] - 'A'].insert(p[2]);

        return solve(bottom);
    }
};

6 评论

panic 2021-09-07 14:50

现在过不了了，
Wrong Answer:
input:”AAAA”
[“AAB”,”AAC”,”BCD”,”BBE”,”DEF”]
Output:true
Expected:false

panic 2021-09-07 14:59

问题主要是在于，比如很高的上层可以合成某个字母比如A，但是他必须是某一条路径合成的，因此底层其他字母被限制了，你的做法是独立判断的每个字母，导致底层被影响的字母没有做判断。我给了一种dp做法，是将一行整体作为判断，可以过。

class Solution {
public:
    unordered_map<string,vector<string>> hash;
    unordered_map<string,bool> state;
    bool dfs(string s){
        //结束
        if (s.size()==1) return true;
        //已经判断过了
        if (state.count(s)) return state[s];
        bool flag=true;
        //找到上一层可能的节点，每次找到两个相邻的点，然后找到对应的上一层可能的点。
        vector<string> nextPossible;
        nextPossible.push_back("");
        for (int i=0;i<s.size()-1;i++){
            string sub=s.substr(i,2);
            //这两个相邻的字母没有出现，肯定不可达
            if (!hash.count(sub)){
                flag=false;
                break;
            }
            vector<string> temp;
            for (string next:hash[sub]){
                for (string ss:nextPossible){
                    temp.push_back(ss+next);
                }
            }
            nextPossible=temp;
        }
        //两个相邻的字母没有出现，肯定不可达
        if (!flag) return state[s]=false;
        //迭代下一层，如果有一个是true表示此方案可达
        for (string s:nextPossible){
            if (dfs(s)) return state[s]=true;
        }
        return state[s]=false;
    }
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for (string &s:allowed) hash[s.substr(0,2)].push_back(s.substr(2));
        return dfs(bottom);
    }
};