[LeetCode] 756. Pyramid Transition Matrix 문제 풀이 보고서 (Python & C + +)

저자: 음 설 명 초 id: fuxuemingzhu 개인 블 로그:http://fuxuemingzhu.cn/
목차
제목 설명
제목
풀이 방법
소 급 법
날짜
제목 주소:https://leetcode.com/problems/pyramid-transition-matrix/description/
제목 설명
We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like 'Z' .
For every block of color C we place not in the bottom row, we are placing it on top of a left block of color A and right block of color B . We are allowed to place the block there only if (A, B, C) is an allowed triple.
We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples allowed. Each allowed triple is represented as a string of length 3.
Return true if we can build the pyramid all the way to the top, otherwise false.
Example 1:

Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
Output: true

Explanation:    

We can stack the pyramid like this:
    A
   / \
  D   E
 / \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.

Example 2:

Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
Output: false

Explanation:
We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.

Note:

bottom will be a string with length in range [2, 8].

allowed will have length in range [0, 200].

Letters in all strings will be chosen from the set {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}.

제목 의 대의
피라미드 의 받침 대 를 제시 하고 의지 할 수 있 는 벽돌 조합 을 제시 했다.피 라 미 드 를 만 들 수 있 을 지.
의존 할 수 있 는 조합 은 앞의 두 문 자 를 바탕 으로 세 번 째 문 자 를 누적 할 수 있다 는 뜻 이다.밤 을 들 어 allowed 의 'XYD' 에 대해 서 는 X 와 Y 를 바탕 으로 D 문 자 를 추가 할 수 있다.
문제 풀이 방법
역 추적 법
처음에는 어렵 다 는 것 을 느 꼈 는데 모델 을 제대로 만 들 지 못 했 기 때문에 이것 은 사실 역 추적 법 을 고찰 하 는 제목 이 었 다.
우선 이 문제 의 난점 이 어디 에 있 는 지 분석 해 보 자.일반적인 역 추적 법 문 제 는 다음 이동 상태 에 대해 명확 하 게 알려 준다. 예 를 들 어 흔히 볼 수 있 는 지도의 4 개 또는 8 개 방향 이다. 그러나 이 문제 의 역 추적 전 이 는 우리 가 간단하게 설계 해 야 한다. 그것 은 두 개의 연속 적 인 문자열 이 생 성 할 수 있 는 모든 세 번 째 문 자 를 목록 에 넣 고 우리 가 다음 에 나 아 갈 방향 으로 삼 는 것 이다.만약 이 이동 상 태 를 다 설계 했다 면 우 리 는 코드 를 쉽게 쓸 수 있 을 것 이다.
우 리 는 각 층 의 문자열 을 밑받침 으로 삼 아 위 에 새로운 층 을 만 들 었 다.그래서 재 귀 과정 이 야.설립 방식 은 허용 되 는 조합 을 통 해 이 조합 은 우리 가 아래 의 이 두 개의 벽돌 을 통 해 위 에 어떤 벽돌 을 누적 할 수 있 는 지 얻 을 수 있 는 방식 이다.
그래서 curr 로 현재 층 을 표시 하고 above 로 상층 을 표시 합 니 다.curr 크기 가 2, above 가 1 이면 피라미드 가 완 성 됩 니 다.만약 curr = above + 1, 위의 이 층 이 이미 다 되 었 음 을 설명 합 니 다. 아래 는 above 를 사용 하여 현재 층 으로 계속 재 귀 합 니 다.
위의 두 글자 가 모두 만족 하지 않 는 다 면 above 를 계속 쌓 아야 한 다 는 뜻 이다. 계속 쌓 여야 할 위치 에서 어떤 문 자 를 쌓 을 수 있 는 지 찾 아 이 문 자 를 쌓 아 재 귀 하 는 방식 이다.
제 가 실 수 를 했 습 니 다. 맵 을 사용 하여 키 값 을 저 장 했 지만 반복 되 는 상황 에 대해 서 는 바 뀌 었 습 니 다.그래서 list 를 사용 해 야 합 니 다. 이 두 벽돌 위 에 쌓 일 수 있 는 벽돌 을 대표 합 니 다.
코드 는 다음 과 같 습 니 다:

class Solution(object):
    def pyramidTransition(self, bottom, allowed):
        """
        :type bottom: str
        :type allowed: List[str]
        :rtype: bool
        """
        m = collections.defaultdict(list)
        for triples in allowed:
            m[triples[:2]].append(triples[-1])
        return self.helper(bottom, "", m)
        
    def helper(self, curr, above, m):
        if len(curr) == 2 and len(above) == 1:
            return True
        if len(above) == len(curr) - 1:
            return self.helper(above, "", m)
        pos = len(above)
        base = curr[pos : pos+2]
        if base in m:
            for ch in m[base]:
                if self.helper(curr, above + ch, m):
                    return True
        return False

C + + 코드 는 다음 과 같 습 니 다.

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        if (bottom.size() == 1) return true;
        for (string& a : allowed) {
            m_[a.substr(0, 2)].push_back(a[2]);
        }
        return helper(bottom, "", m_);
    }
private:
    unordered_map<string, vector<char>> m_;
    bool helper(string pre, string cur, unordered_map<string, vector<char>>& m_) {
        if (pre.size() == 2 && cur.size() == 1) return true;
        if (pre.size() - cur.size() == 1)
            return helper(cur, "", m_);
        int pos = cur.size();
        string next = pre.substr(pos, 2);
        for (char cs : m_[next]) {
            if (helper(pre, cur + cs, m_)) {
                return true;
            }
        }
        return false;
    }
};

참고 자료:
http://www.cnblogs.com/grandyang/p/8476646.html
날짜.
2018 년 9 월 6 일 - 일과 휴식 이 점점 규칙 적 이다.2019 년 1 월 25 일 - 이번 학기 마지막 근무일