最长公共前缀可以使用字典树来解答，在解答中，需要查找单词，如果有精确需要查找的单词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]*TrieNode
isEnd 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 := 0
for 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]*Trie
isEnd 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, i+1) {
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]*WordDictionary
isEnd 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, i+1) {
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);
*/
