装饰设计资质等级标准,怎么做网站优化,网上交易系统,lnmp wordpress 500最长公共前缀可以使用字典树来解答#xff0c;在解答中#xff0c;需要查找单词#xff0c;如果有精确需要查找的单词word#xff0c;那么可以使用代码#xff1a;
func (this *Trie) Search(word string) bool {for _, v : range word {if this.next[v-a] nil {return …最长公共前缀可以使用字典树来解答在解答中需要查找单词如果有精确需要查找的单词word那么可以使用代码
func (this *Trie) Search(word string) bool {for _, v : range word {if this.next[v-a] nil {return false}this this.next[v-a]}if this.isEnd false {return false}return true
}但是如果查找的单词不明确那么可以使用代码以公共前缀为例
func (node *TrieNode) search() string {prefix : for node.countChildren() 1 !node.isEnd {//就是这个位置可以遍历字典树中的字母如果当前字母不为空可以继续往下遍历for i : 0; i 26; i {if node.next[i] ! nil {prefix prefix string(a i)node node.next[i]break}}}return prefix
}// 计算当前节点子节点的数量
func (node *TrieNode) countChildren() int {......
}最长公共前缀 简单 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀返回空字符串 “”。 示例 1 输入strs [“flower”,“flow”,“flight”] 输出“fl” 示例 2 输入strs [“dog”,“racecar”,“car”] 输出“” 解释输入不存在公共前缀。 //字符串
// 函数首先找到长度最短的字符串然后逐个比较字符如果遇到不相同的字符则返回当前索引之前的字符串作为结果。
//这是一个更简洁的实现它的时间复杂度是O(n*m)其中n是字符串数组的长度m是字符串的平均长度。func longestCommonPrefix(strs []string) string {if len(strs) 0 {return }minstr : strs[0]for _, str : range strs {if len(str) len(minstr) {minstr str}}for i : 0; i len(minstr); i {curStr : strs[0][i]for _, str : range strs {if str[i] ! curStr {return strs[0][:i]}}}return strs[0][:len(minstr)]
}//使用字典树
type TrieNode struct {next [26]*TrieNodeisEnd bool
}func longestCommonPrefix(strs []string) string {root : TrieNode{}//构建字典树for _, str : range strs {root.Insert(str)}//查找最长公共前缀return root.search()
}// 插入字符
func (node *TrieNode) Insert(word string) {for _, v : range word {if node.next[v-a] nil {node.next[v-a] TrieNode{}}node node.next[v-a]}node.isEnd true
}//查找字符和公共前缀
func (node *TrieNode) search() string {prefix : //当前节点的子节点数量为1(如果大于1表示节点之后会有分叉就不是公共节点)//且当前节点不是一个单词的结束节点就继续循环。for node.countChildren() 1 !node.isEnd {for i : 0; i 26; i {if node.next[i] ! nil {prefix prefix string(a i)node node.next[i]break}}}return prefix
}// 计算当前节点子节点的数量
func (node *TrieNode) countChildren() int {count : 0for i : 0; i 26; i {if node.next[i] ! nil {count}}return count
} 实现 Trie (前缀树) 中等 Trie发音类似 “try”或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补完和拼写检查。 请你实现 Trie 类 Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 word 。 boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。 boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。 示例 输入 [“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”] [[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]] 输出 [null, null, true, false, true, null, true] 解释 Trie trie new Trie(); trie.insert(“apple”); trie.search(“apple”); // 返回 True trie.search(“app”); // 返回 False trie.startsWith(“app”); // 返回 True trie.insert(“app”); trie.search(“app”); // 返回 True type Trie struct {next [26]*TrieisEnd bool
}func Constructor() Trie {return Trie{}
}func (this *Trie) Insert(word string) {for _, v : range word {if this.next[v-a] nil {this.next[v-a] new(Trie)}this this.next[v-a]}this.isEnd true
}func (this *Trie) Search(word string) bool {for _, v : range word {if this.next[v-a] nil {return false}this this.next[v-a]}if this.isEnd false {return false}return true
}//前提是已经知道 prefix 这个单词因此和前面“查找公共前缀”的解答不一样遍历过程不一样和开头中提到的精确到具体单词类似
func (this *Trie) StartsWith(prefix string) bool {for _, v : range prefix {if this.next[v-a] nil {return false}this this.next[v-a]}return true
}/*** Your Trie object will be instantiated and called as such:* obj : Constructor();* obj.Insert(word);* param_2 : obj.Search(word);* param_3 : obj.StartsWith(prefix);*/下面这道题解答过程和 “实现 Trie (前缀树)” 的insert和search基本一样主要区别在于查找单词时多了条件word 中可能包含一些 ‘.’ 每个 . 都可以表示任何一个字母。 多添加的代码是判断.的情况
if char . {for _, v : range this.next {if v ! nil v.search(word, i1) {return true}}return false}添加与搜索单词 - 数据结构设计 中等 请你设计一个数据结构支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 WordDictionary WordDictionary() 初始化词典对象 void addWord(word) 将 word 添加到数据结构中之后可以对它进行匹配 bool search(word) 如果数据结构中存在字符串与 word 匹配则返回 true 否则返回 false 。word 中可能包含一些 ‘.’ 每个 . 都可以表示任何一个字母。 示例 输入 [“WordDictionary”,“addWord”,“addWord”,“addWord”,“search”,“search”,“search”,“search”] [[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b…”]] 输出 [null,null,null,null,false,true,true,true] 解释 WordDictionary wordDictionary new WordDictionary(); wordDictionary.addWord(“bad”); wordDictionary.addWord(“dad”); wordDictionary.addWord(“mad”); wordDictionary.search(“pad”); // 返回 False wordDictionary.search(“bad”); // 返回 True wordDictionary.search(“.ad”); // 返回 True wordDictionary.search(“b…”); // 返回 True type WordDictionary struct {next [26]*WordDictionaryisEnd bool
}func Constructor() WordDictionary {return WordDictionary{}
}func (this *WordDictionary) AddWord(word string) {for _, v : range word {if this.next[v-a] nil {this.next[v-a] new(WordDictionary)}this this.next[v-a]}this.isEnd true
}func (this *WordDictionary) Search(word string) bool {return this.search(word, 0)
}func (this *WordDictionary) search(word string, index int) bool {for i : index; i len(word); i {char : word[i]//多了判断.的情况其他基本一致if char . {for _, v : range this.next {if v ! nil v.search(word, i1) {return true}}return false}if this.next[char-a] nil {return false}this this.next[char-a]}if this.isEnd false {return false}return true
}/*** Your WordDictionary object will be instantiated and called as such:* obj : Constructor();* obj.AddWord(word);* param_2 : obj.Search(word);*/
