省市区过滤-526互联

题目：

省市区过滤
某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

输出
符合条件的全路径数量


思路：
注意到匹配要求可以转化为 char2count，所以直接打散输入进行匹配。
之后注意到结果其实是要求查树的子节点，这里为了方便直接构建出树并使用bfs。


package main

import (
	"fmt"
)

type Area struct {
	Area     string
	BelongTo string
}

type AreaNode struct {
	Area       string
	BelongTo   string
	Parent     *AreaNode
	ChildNodes []*AreaNode
}

type AreaTree struct {
	areaToNode map[string]*AreaNode
}

func (t *AreaTree) AddArea(area Area) {
	areaNode := &AreaNode{Area: area.Area, BelongTo: area.BelongTo}
	t.areaToNode[area.Area] = areaNode
	t.areaToNode[area.BelongTo] = areaNode
}

func (t *AreaTree) FindNode(areaStr string) *AreaNode {
	if node, ok := t.areaToNode[areaStr]; ok {
		return node
	}
	return nil
}

func (t *AreaTree) FindFootNode(areaNode *AreaNode, footNodeSet *map[string]bool) {
	for _, childNode := range areaNode.ChildNodes {
		(*footNodeSet)[childNode.Area] = true
		t.FindFootNode(childNode, footNodeSet)
	}
}

func (n *AreaNode) AddChildNode(childNode *AreaNode) {
	n.ChildNodes = append(n.ChildNodes, childNode)
}

func (n *AreaNode) HasChildNode() bool {
	return len(n.ChildNodes) > 0
}

func areaMatchKeyWord(area Area, keyword string) bool {
	keywordCharCount := make(map[rune]int)
	for _, char := range keyword {
		keywordCharCount[char]++
	}
	areaCharCount := make(map[rune]int)
	for _, char := range area.Area {
		areaCharCount[char]++
	}
	for _, char := range area.BelongTo {
		areaCharCount[char]++
	}
	for char, count := range keywordCharCount {
		if areaCharCount[char] < count {
			return false
		}
	}
	return true
}

func matchPaths(areas []Area, keyword string) int {
	areaTree := &AreaTree{areaToNode: make(map[string]*AreaNode)}
	areaMatchSet := make(map[string]bool)
	for _, area := range areas {
		areaTree.AddArea(area)
	}
	for _, area := range areas {
		if areaMatchKeyWord(area, keyword) {
			areaMatchSet[area.Area] = true
			areaMatchSet[area.BelongTo] = true
		}
	}
	footNodeSet := make(map[string]bool)
	for areaStr := range areaMatchSet {
		areaNode := areaTree.FindNode(areaStr)
		footNodeSet[areaNode.Area] = true
		areaTree.FindFootNode(areaNode, &footNodeSet)
	}
	var count int
	for areaStr := range footNodeSet {
		if !areaTree.FindNode(areaStr).HasChildNode() {
			count++
		}
	}
	return count
}

func main() {
	areas := []Area{
		{Area: "Area1", BelongTo: "BelongTo1"},
		{Area: "Area2", BelongTo: "BelongTo2"},
	}

	keyword := "Area1"

	count := matchPaths(areas, keyword)

	fmt.Println("Count:", count)
}