756. Pyramid Transition Matrix

发表于 | 分类于

题目详见：https://leetcode.com/problems/pyramid-transition-matrix/

思路：递归，回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string,vector<char>> allowed_map;
        for(string element:allowed){            
            allowed_map[element.substr(0,2)].push_back(element.back());            
        }
        string current="";
        return DFS(bottom,current,0,allowed_map);
    }
private:
    //两个字母用一个字母代替
    //pre未替换完的字符串
    //current当前已替换完得到的字符串
    //k,pre开始要替换的字母的index
    //dict包含可替换的选择
    bool DFS(string& pre,string& current,int k,unordered_map<string,vector<char>>& dict){
        if(pre.length()==1) return true;
        if(k+1==pre.length()){
            string next="";
            return DFS(current,next,0,dict);
        }
        else{
            string key=pre.substr(k,2);
            if(dict.count(key)==0) return false;
            vector<char> value=dict[key];
            for(auto c:value){
                current.push_back(c);
                if(DFS(pre,current,k+1,dict)) return true;
                current.pop_back();
            }
            return false;
        }
            
    }    
};