2021-02-21：手寫代碼：高性能路由，也就是一個(gè)字符串和多個(gè)
2021-02-21：手寫代碼：高性能路由，也就是一個(gè)字符串和多個(gè)匹配串進(jìn)行模糊匹配。一個(gè)數(shù)組arr里是["*a*","moonfdd"]，字符串"moonfdd"能匹配到，理由是arr里有。字符串"xayy"也能匹配到，理由是arr里的"*a*"，第1個(gè)星對(duì)應(yīng)"x"，第2個(gè)星對(duì)應(yīng)"yy"。
福哥答案2021-02-21：
1.前綴樹。字符匹配和星號(hào)匹配。abcd和ab*cd,當(dāng)左c和右*對(duì)應(yīng)的時(shí)候，下一步分兩種情況，左d和右*對(duì)應(yīng)，左c和右c對(duì)應(yīng)。有代碼。
2.ACOK算法。當(dāng)時(shí)和面試官聊的時(shí)候，面試官說(shuō)了ACOK算法，但這個(gè)算法在網(wǎng)上沒(méi)找到。百度了一番，感覺(jué)就是Aho-Corasick automaton算法，也就是AC自動(dòng)機(jī)。AC自動(dòng)機(jī)，沒(méi)找到解法，所以沒(méi)代碼。
代碼用golang編寫，代碼如下：
```go
package main
import "fmt"
func main() {
? ? fmt.Println("力扣208 測(cè)試")
? ? trie := Constructor()
? ? trie.Insert("apple")
? ? trie.Search("apple")? ?// 返回 true
? ? trie.Search("app")? ? ?// 返回 false
? ? trie.StartsWith("app") // 返回 true
? ? trie.Insert("app")
? ? trie.Search("app") // 返回 true
? ? fmt.Println("--------------------")
? ? fmt.Println("高性能路由 測(cè)試")
? ? ret := ""
? ? ret = RouteMatching("fudada", []string{"fudada*"})
? ? fmt.Println("ret = ", ret)
? ? ret = RouteMatching("fudada", []string{"fu******da*"})
? ? fmt.Println("ret = ", ret)
? ? ret = RouteMatching("fudada", []string{"fudada**"})
? ? fmt.Println("ret = ", ret)
}
type TrieNode struct {
? ? pass? ? int
? ? end? ? ?int
? ? nextMap map[byte]*TrieNode
}
type Trie struct {
? ? root *TrieNode
}
/** Initialize your data structure here. */
func Constructor() Trie {
? ? return Trie{root: &TrieNode{nextMap: make(map[byte]*TrieNode)}}
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
? ? wordLen := len(word)
? ? if wordLen == 0 {
? ? ? ? return
? ? }
? ? node := this.root
? ? node.pass++
? ? for i := 0; i < wordLen; i++ { // 從左往右遍歷字符
? ? ? ? if node.nextMap[word[i]] == nil {
? ? ? ? ? ? node.nextMap[word[i]] = &TrieNode{nextMap: make(map[byte]*TrieNode)}
? ? ? ? }
? ? ? ? node = node.nextMap[word[i]]
? ? ? ? node.pass++
? ? }
? ? node.end++
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
? ? wordLen := len(word)
? ? if wordLen == 0 {
? ? ? ? fmt.Println(false)
? ? ? ? return false
? ? }
? ? node := this.root
? ? for i := 0; i < wordLen; i++ { // 從左往右遍歷字符
? ? ? ? if node.nextMap[word[i]] == nil {
? ? ? ? ? ? fmt.Println(false)
? ? ? ? ? ? return false
? ? ? ? }
? ? ? ? node = node.nextMap[word[i]]
? ? }
? ? fmt.Println(node.end > 0)
? ? return node.end > 0
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
? ? word := prefix
? ? wordLen := len(word)
? ? if wordLen == 0 {
? ? ? ? fmt.Println(false)
? ? ? ? return false
? ? }
? ? node := this.root
? ? for i := 0; i < wordLen; i++ { // 從左往右遍歷字符
? ? ? ? if node.nextMap[word[i]] == nil {
? ? ? ? ? ? fmt.Println(false)
? ? ? ? ? ? return false
? ? ? ? }
? ? ? ? node = node.nextMap[word[i]]
? ? }
? ? fmt.Println(node.pass > 0)
? ? return node.pass > 0
}
func RouteMatching(url string, fuzzyMatches []string) string {
? ? fuzzyMatchesLen := len(fuzzyMatches)
? ? if fuzzyMatchesLen == 0 && len(url) == 0 {
? ? ? ? return ""
? ? }
? ? trie := Constructor()
? ? for i := 0; i < fuzzyMatchesLen; i++ {
? ? ? ? trie.Insert(fuzzyMatches[i])
? ? }
? ? return process(url, 0, trie.root, "")
}
func process(url string, index int, root *TrieNode, retPre string) string {
? ? urlLen := len(url)
? ? if index >= urlLen {
? ? ? ? if root.end > 0 {
? ? ? ? ? ? return retPre
? ? ? ? } else {
? ? ? ? ? ? if root.nextMap['*'] != nil {
? ? ? ? ? ? ? ? return process(url, index, root.nextMap['*'], retPre+"*")
? ? ? ? ? ? }
? ? ? ? ? ? return ""
? ? ? ? }
? ? }
? ? ret := ""
? ? //1.匹配字符
? ? if root.nextMap[url[index]] != nil {
? ? ? ? ret = process(url, index+1, root.nextMap[url[index]], retPre+url[index:index+1])
? ? ? ? if ret != "" {
? ? ? ? ? ? return ret
? ? ? ? }
? ? }
? ? //2.匹配*
? ? if root.nextMap['*'] != nil {
? ? ? ? ret = process(url, index, root.nextMap['*'], retPre+"*")
? ? ? ? if ret != "" {
? ? ? ? ? ? return ret
? ? ? ? }
? ? ? ? ret = process(url, index+1, root, retPre)
? ? ? ? if ret != "" {
? ? ? ? ? ? return ret
? ? ? ? }
? ? }
? ? return ret
}
```
執(zhí)行結(jié)果如下：
***
[左神前綴樹java代碼](https://github.com/algorithmzuo/trainingcamp002/blob/master/src/class08/Code01_AC.java)
[評(píng)論](https://user.qzone.qq.com/3182319461/blog/1613864447)
