Go递归

Question

我是一名Javascript开发人员，他决定给Go一个旋转。作为一个学习练习，我决定在我的一个节点项目中移植一个函数，但无法为我的生活工作。该功能的目的是显示所有有效的英语单词，这些单词可以用不同单词中的字母（我正在构建多人游戏版本Text Twist）制作。例如，findAllWords（“舞蹈”）会返回['can'，'scan'，'dance'，'dances'等]。我通过递归从英文单词列表构建的单词树实现了这一点。

这是在JavaScript中函数的实现：

self.findAllWords = function(letters = [], trie = dictionary, curString = '') { 
    let words = []; 
    letters = typeof letters === 'string' ? letters.split('') : letters; 
    letters.forEach((letter,i,ar) => { 
     if (!trie[letter]) return; 
     let curWord = curString + letter; 
     let newTrie = trie[letter]; 
     let newLetters = [...ar.slice(0,i),...ar.slice(i+1)]; 
     if (trie[letter][FLAG_INDEX]) words.push(curWord); 
     if (self.isValidPrefix(curWord, dictionary)) words = [...words,...self.findAllWords(newLetters,newTrie,curWord)]; 
    }); 
    return uniq(words); 
} 

，这里是我的企图在去复制它（使用this特里实现）：

func FindAllWords(letters []rune, node *Node, curString string) []string { 

words := []string{} 
for i, let := range letters { 
    n, ok := node.Children()[let] 

    if !ok { 
     return words 
    } 
    curWord := curString + string(n.val) 
    newLetters := []rune{} 
    newLetters = append(newLetters, letters[:i]...) 
    newLetters = append(newLetters, letters[i+1:]...) 

    if n.term { 
     words = append(words, curWord) 
    } 

    words = append(words, FindAllWords(newLetters, n, curWord)...) 
} 
return words 
} 

很想知道这是为什么失败，如何让它工作，以及我滥用/不使用的任何约定。谢谢！

Answer 1

这可能是也可能不是Go代码的唯一问题，但for循环中的return语句与javascript forEach中的return语句没有做同样的事情。

返回匿名函数中的javascript代码从匿名函数返回到findAllWords函数中。在Go for循环中返回从FindAllWords返回。当它遇到不在字根的字母时，这会过早地停止操作。我认为你遇到的问题是[]string被返回是空的或不完整的。您可以使用break而不是return words。

Answer 2

OK，有两个问题在OP的实现：

• if块检查孩子存在的行动应该“继续”的循环，而不是返回的话，结果（尝试其他的树枝） 。
• if block条件检查当前节点是否是终端（字）必须改变，以适应github.com/derekparker/trie作者的设计决定，将终端节点存储为与最后一个字母对应的节点的子节点这个词，作为0符文在其父母中键入。

这里的工作版本：

func FindAllWords(letters []rune, node *trie.Node, curString string) []string { 
    words := []string{} 
    for i, let := range letters { 
     n, ok := node.Children()[let] 
     if !ok { 
      continue 
     } 
     curWord := curString + string(n.Val()) 
     newLetters := []rune{} 
     newLetters = append(newLetters, letters[:i]...) 
     newLetters = append(newLetters, letters[i+1:]...) 
     if n.Children()[0x0] != nil { 
      words = append(words, curWord) 
     } 
     words = append(words, FindAllWords(newLetters, n, curWord)...) 
    } 
    return words 
} 

这里有一个稍微更可读的版本（合我的口味，当然）：

func FindAllWords2(s string, n *trie.Node, w string) []string { 
    r := []string{} 
    for i, l := range s { 
     n1, ok := n.Children()[l] 
     if !ok { 
      continue 
     } 
     s1 := s[:i] + s[i+1:] 
     w1 := w + string(l) 
     if n1.Children()[0x0] != nil { 
      r = append(r, w1) 
     } 
     r = append(r, FindAllWords2(s1, n1, w1)...) 
    } 
    return r 
} 

第二个问题当然是从依赖于未来的一个具有漏洞的API的外部库，它将实现细节公开给客户端代码。

为了避免这样那样的麻烦，这个简单的例子，我建议建立一个简单的线索实现能来，因为这很容易：

type Node struct { 
    Char  rune 
    Term  bool 
    Children map[rune]*Node 
} 

func (n *Node) Add(s []rune) { 
    if len(s) == 0 { 
     n.Term = true 
     return 
    } 
    r := s[0] 
    c, ok := n.Children[r] 
    if !ok { 
     c = &Node{Char: r, Children: make(map[rune]*Node)} 
     n.Children[r] = c 
    } 
    c.Add(s[1:]) 
} 

func Empty() *Node { 
    return &Node{Children: make(map[rune]*Node)} 
} 

使用结构，这是我如何装载一个英语单词表：

func English() *Node { 
    f, err := os.Open("/usr/share/dict/american-english") 
    if err != nil { 
     panic(err) 
    } 
    defer f.Close() 
    t := Empty() 
    s := bufio.NewScanner(f) 
    for s.Scan() { 
     t.Add([]rune(strings.ToLower(s.Text()))) 
    } 
    return t 
} 

这种结构可以在同一个算法中使用极少的修改，并没有实现misteries：

func FindAllWords3(s string, n *Node, w string) []string { 
    r := []string{} 
    for i, l := range s { 
     n1, ok := n.Children[l] 
     if !ok { 
      continue 
     } 
     s1 := s[:i] + s[i+1:] 
     w1 := w + string(l) 
     if n1.Term { 
      r = append(r, w1) 
     } 
     r = append(r, FindAllWords3(s1, n1, w1)...) 
    } 
    return r 
} 

以下是上述加于字“舞”和上面加载相同的单词表英语的三种实现的结果：

[d dan dance dances dane danes dean deans den dena dens dec a ad aden ads an and andes ac acne ace aced aces as ascend n nd na ne ned c cd ca cad cads can cane caned canes cans case cased cs e ed edna end ends es s sad sade san sand sane sac sn snead sc scad scan se sedan sedna sea sean sen send sec] 
[d dan dance dances dane danes dean deans den dena dens dec a ad aden ads an and andes ac acne ace aced aces as ascend n nd na ne ned c cd ca cad cads can cane caned canes cans case cased cs e ed edna end ends es s sad sade san sand sane sac sn snead sc scad scan se sedan sedna sea sean sen send sec] 
[d dan dance dances dane danes dean deans den dena dens dec a ad aden ads an and andes ac acne ace aced aces as ascend n nd na ne ned c cd ca cad cads can cane caned canes cans case cased cs e ed edna end ends es s sad sade san sand sane sac sn snead sc scad scan se sedan sedna sea sean sen send sec]