关于福大大架构师每日一题:20210221手写代码高性能路由也就是一个字符串和多个匹配串进行模糊匹配

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 mainimport "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代码
评论