LeetCode Solutions
class Solution {
public:
bool pyramidTransition(string bottom, vector<string>& allowed) {
unordered_map<string, vector<char>> prefixToBlocks;
for (const string& a : allowed)
prefixToBlocks[a.substr(0, 2)].push_back(a[2]);
return dfs(bottom, "", 0, prefixToBlocks);
}
private:
bool dfs(const string& row, const string& nextRow, int i,
const unordered_map<string, vector<char>>& prefixToBlocks) {
if (row.length() == 1)
return true;
if (nextRow.length() + 1 == row.length())
return dfs(nextRow, "", 0, prefixToBlocks);
const string& prefix = row.substr(i, 2);
if (prefixToBlocks.count(prefix))
for (const char c : prefixToBlocks.at(prefix))
if (dfs(row, nextRow + c, i + 1, prefixToBlocks))
return true;
return false;
}
};
|
class Solution {
public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String, List<Character>> prefixToBlocks = new HashMap<>();
for (final String a : allowed) {
final String lowerBlocks = a.substring(0, 2);
prefixToBlocks.putIfAbsent(lowerBlocks, new LinkedList<>());
prefixToBlocks.get(lowerBlocks).add(a.charAt(2));
}
return dfs(bottom, "", 0, prefixToBlocks);
}
private boolean dfs(final String row, final String nextRow, int i,
Map<String, List<Character>> prefixToBlocks) {
if (row.length() == 1)
return true;
if (nextRow.length() + 1 == row.length())
return dfs(nextRow, "", 0, prefixToBlocks);
final String prefix = row.substring(i, i + 2);
if (prefixToBlocks.containsKey(prefix))
for (final char c : prefixToBlocks.get(prefix))
if (dfs(row, nextRow + c, i + 1, prefixToBlocks))
return true;
return false;
}
}
|
class Solution:
def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
prefixToBlocks = defaultdict(list)
for a in allowed:
prefixToBlocks[a[:2]].append(a[2])
def dfs(row: str, nextRow: str, i: int) -> bool:
if len(row) == 1:
return True
if len(nextRow) + 1 == len(row):
return dfs(nextRow, '', 0)
for c in prefixToBlocks[row[i:i + 2]]:
if dfs(row, nextRow + c, i + 1):
return True
return False
return dfs(bottom, '', 0)
|
