Perform Longest Common Prefix

Question

I'm working on a Leetcode exercise in regards to finding the Longest Common Prefix in an array of words. Working on improving my skill in Golang and so attempting it in that language. I'm attempting to solve it using a Trie structure. I've racked my brain and am unsure why my counter that keeps track of how many times a node is visited is not incrementing in my struct. My brain thinks its something pointer/reference related but when I look at it, it seems fine.

My thought process is that if you encounter a node that has already been created, you increment its "visited" counter by one. Then, if you determine that the node has been visited the same amount of times as the number of words in the input array and its greater than current LCP, then make that the new LCP.

The issue I'm having is the counter in the Node is not incrementing. When I increment it and then immediately print the value, it appears to have incremented but then when its traveled to in the next iteration, its value has not increased from its original initialized value of 1

func longestCommonPrefix(strs []string) string {
rootNode := Node {CommonPrefixCounter: 0, LinkNodes: make(map[string]Node, 26) }
var currentNode Node
longestPrefix := ""
lengthOfLongestPrefix := 0
if(len(strs) == 1) {
    //Edge case where there is only one word so whatever its length is longest common prefix
    return strs[0]
}
for _, word := range strs {
    currentNode = rootNode
    currentPrefix := ""
    //Split into individual character
    characters := strings.Split(word, "")
    for _, character := range characters {
        fmt.Printf("Current Letter is %s \n", character)
        if currentNode.LinkNodes[character].LinkNodes == nil {
            //Have not seen this letter in this sequence before
            fmt.Println("Making a new node")
            currentNode.LinkNodes[character] = Node{CommonPrefixCounter: 1, LinkNodes: make(map[string]Node, 26)}
            currentNode = currentNode.LinkNodes[character]
        }  else {
            //Have encountered this Node before
            currentPrefix += character
            currentNode = currentNode.LinkNodes[character]
            currentNode.CommonPrefixCounter++
            fmt.Printf("CurrentNode common prefix counter is %d\n", currentNode.CommonPrefixCounter)
            if (currentNode.CommonPrefixCounter > lengthOfLongestPrefix) && currentNode.CommonPrefixCounter == len(strs) {
                lengthOfLongestPrefix = currentNode.CommonPrefixCounter
                longestPrefix = currentPrefix
            }
        }
    }
}
fmt.Printf("Longest Common Prefix was %d and it was %s", lengthOfLongestPrefix + 1, longestPrefix )
return longestPrefix

}

type Node struct {
CommonPrefixCounter int
LinkNodes map[string]Node

}

Any help would be appreciated. Sitting here looking at it for a few hours and decided its time for some help.

score 0 · Answer 1 · answered Nov 02 '22 at 17:31

Your maps are using nodes as value. That means, any time you get a node value from the map, you get a copy of it, and any time you put a value, you put a copy of it. Because of this, currentNode.CommonPrefixCounter++ will update the currentNode copy you have but not the copy in the map.

Declare the map as map[string]*Node and pass node pointers around. There might be other bugs in your code, but this would at least allow you to create a correct trie.

Perform Longest Common Prefix

1 Answers1