省市区过滤

省市区过滤

题目描述

某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，输出符合条件的全路径数量。

用例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

解题思路

思路：

1. 构建树
2. 判断是否满足匹配
3. dfs递归判断

实现代码

很自然的想到构建多叉树，然后根据输入去构建一棵多叉树，然后生成它。

#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;
}