省市区过滤
题目描述
某web应用系统在登记信息时需要选择省市区，当省市区数量过多时，需要根据关键字模糊匹配、筛选出想要选择的地区。 现给定某个国家的系列地区名称及其归属地，记录于数组areas中， areas[i]=[area,belongTo]，这些地区的关系形成一棵树。请计算并返回符合条件的全路径数量（可能为0）； 一个地区的名称若包含关键字keyword中的所有字符（多个相同字符需要包含多次）， 则被称为【匹配地区】，例如keyword未"ZSEE"，地区 “SHENZHEN”是匹配地区，地区“SHENZHN”不是匹配地区。 一条全路径时从根到叶（含根和叶），路径上至少一个节点是匹配地区。
输入第一个参数为areas，1<=areas.length<=100，每个元素的area和belongTo均为大写字母组成的字符串， 长度范围均为[1,10]，且areas[i]，area不重复，输入保证areas是一棵树的边的全集 第二个参数是字符串keyword，均为大写字母，1<=keyword.length<=10，输出符合条件的全路径数量。
代码语言：javascript复制用例1：
输入：[["SCQ", "ZHSZH"], ["XCQ", "ZHSZH"], ["ZH", "WWS"], ["ZHSZH", "QJS"], ["WWS", "QJS"], ["WW", "XCQ"]]
"ZZH"
输出：2
QJS
|- ZHSZH
|- SCQ
|- XCQ
|- WW
|- WWS
|- ZH用例2：
输入：[["HA", "A"], ["HC", "A"], ["D", "HA"], ["HD", "D"]]
"H"
输出：2
A
|- HA
|- D
|- HD
|- HC解题思路
思路：
- 构建树
- 判断是否满足匹配
- dfs递归判断
实现代码
很自然的想到构建多叉树，然后根据输入去构建一棵多叉树，然后生成它。
代码语言：javascript复制#include <unordered_map>
#include <vector>
#include <string>
#include <iostream>
using std::unordered_map;
using std::vector;
struct TreeNode
{
TreeNode *parent = nullptr; // 父节点
std::vector<TreeNode*> children; // 孩子节点数组
bool isMatched = false; // 是否满足匹配地区的条件
};
class Solution
{
private:
std::unordered_map<char, int> keyWordMap; // 关键字的字符个数计数map
TreeNode *root;
int count = 0;
public:
int MatchPaths(const std::vector<std::pair<std::string, std::string>> &areas,
const std::string &keyword)
{
keyWordMap = GetStringMap(keyword);
root = CreateTree(areas);
dfs(root, false);
return count;
}
TreeNode* CreateTree(const std::vector<std::pair<std::string, std::string>> &areas)
{
// 临时存放treeNode，用于快速构建树
std::unordered_map<std::string, TreeNode*> tmpMap;
for (int i = 0; i < areas.size(); i ) {
// 1. 判断并构建父节点
auto pParent = tmpMap.find(areas[i].second);
TreeNode *parentNode = nullptr;
if (pParent == tmpMap.end()) {
parentNode = new TreeNode;
// 判断是否是满足条件的节点
parentNode->isMatched = ContainKeyword(GetStringMap(areas[i].second));
tmpMap.insert({ areas[i].second, parentNode });
} else {
parentNode = pParent->second;
}
// 2. 查找或构建当前节点
auto current = tmpMap.find(areas[i].first);
TreeNode *currentNode = nullptr;
if (current == tmpMap.end()) {
currentNode = new TreeNode;
// 判断是否是满足条件的节点
currentNode->isMatched = ContainKeyword(GetStringMap(areas[i].first));
tmpMap.insert({ areas[i].first, currentNode });
} else {
currentNode = current->second;
}
// 3. 构建父子节点关系
currentNode->parent = parentNode;
parentNode->children.push_back(currentNode);
}
// 4. 查找根节点，注意：根节点的parent父节点为空
for (auto &item : tmpMap)
{
if (item.second->parent == nullptr) {
return item.second;
}
}
return nullptr;
}
// 将字符串转换为map，用于判断是否满足匹配条件
std::unordered_map<char, int> GetStringMap(const std::string &keyword)
{
std::unordered_map<char, int> resultMap;
for (auto ch : keyword) {
resultMap[ch] ;
}
return resultMap;
}
// 查看原map是否包含keyWordMap中的所有字符
bool ContainKeyword(const std::unordered_map<char, int> &source)
{
for (const auto &item : keyWordMap)
{
auto iter = source.find(item.first);
if (iter == source.end() || iter->second < item.second)
{
return false;
}
}
return true;
}
// 遍历树节点，查找可能存在的路径数量，flag表示父节点中是否存在匹配的节点
void dfs(TreeNode *root, bool flag)
{
if (!root->children.empty())
{
for (auto node : root->children)
{
dfs(node, flag | root->isMatched);
}
return;
}
if (root->isMatched | flag)
{
count ;
}
}
void Remove(TreeNode *root)
{
if (root == nullptr) {
return;
}
if (root->children.empty()) {
for (auto iter = root->children.begin(); iter != root->children.end();) {
Remove(*iter);
iter = root->children.erase(iter);
}
}
delete root;
}
virtual ~Solution()
{
Remove(root);
}
};
int main()
{
// D -> HA
// BAX -> SHENZHEN
// HA -> CXQ
// D -> BAX
Solution sol;
std::vector<std::pair<std::string, std::string>> areas = {
{"HA", "D"},
{"SHENZHEN", "BAX"},
{"CXQ", "HA"},
{"BAX", "D"}
};
// D
// |- HA
// |- CXQ
// |- BAX
// |- SHENZHEN
std::string keyword = "ZSEE"; // ZSEE 1
// A 2
// D 2
int resultCnt = sol.MatchPaths(areas, keyword);
std::cout << resultCnt << std::endl;
return 0;
}
