2021-02-21:手写代码:高性能路由,也就是一个字符串和多个匹配串进行模糊匹配
2014 年 9 月 4 日
2021-02-21:手写代码:高性能路由,也就是一个字符串和多个匹配串进行模糊匹配。一个数组arr里是[” a “,”moonfdd”],字符串”moonfdd”能匹配到,理由是arr里有。字符串”xayy”也能匹配到,理由是arr里的” a “,第1个星对应”x”,第2个星对应”yy”。
福哥答案2021-02-21:
1.前缀树。字符匹配和星号匹配。abcd和ab cd,当左c和右 对应的时候,下一步分两种情况,左d和右*对应,左c和右c对应。有代码。
2.ACOK算法。当时和面试官聊的时候,面试官说了ACOK算法,但这个算法在网上没找到。百度了一番,感觉就是Aho-Corasick automaton算法,也就是AC自动机。AC自动机,没找到解法,所以没代码。
代码用golang编写,代码如下:
package main import "fmt" func main() { fmt.Println("力扣208 测试") 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("高性能路由 测试") 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 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 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 = 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 }
执行结果如下: