2021-02-21：手写代码：高性能路由，也就是一个字符串和多个匹配串进行含糊匹配。一个数组 arr 里是[“a“,”moonfdd”]，字符串 ”moonfdd” 能匹配到，理由是 arr 里有。字符串 ”xayy” 也能匹配到，理由是 arr 里的 ”a“，第 1 个星对应 ”x”，第 2 个星对应 ”yy”。
福哥答案 2021-02-21：
1. 前缀树。字符匹配和星号匹配。abcd 和 abcd, 当左 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 < 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
}
执行后果如下：
左神前缀树 java 代码
评论