Quick Go solution (12 ms) - a walk through the trellis


  • 0
    E

    First, we create a map from the runes of ring to their positions in ring. Then we walk through the runes of key, keeping track of potentially optimal paths and how many steps they require.

    At step 0, we identify the rune at key[0]. We find all the locations of this rune in ring (let's say n locations), and count the steps required for each location. We now have n potential paths.

    At step 1, we must move along our n potential paths to the rune at key[1]. Let's say the rune at key[1] shows up in ring m times. So there are now n*m potentially optimal paths. But at each location of key[1] in ring, we only care about the best incoming path and we can discard the rest. So now we have m possible paths.

    We continue in this way until we reach the last character of key. If it shows up p times in ring, corresponding to p potential paths, we choose the path with the minimum number of steps, and return its step count.

    import "math"
    
    func min(i, j int) int {
        if i < j {
            return i
        }
        return j
    }
    
    func abs(i int) int {
        if i < 0 {
            return -i
        }
        return i
    }
    
    type path struct {
        steps int
        ind int
    }
    
    func findRotateSteps(ring string, key string) int {
        
        // map each rune to its location(s) in ring
        runeInds := make(map[rune][]int)
        for i, r := range ring {
            runeInds[r] = append(runeInds[r], i)
        }
        
        var bestPath path
        n := len(ring)
        prevPaths := []path{path{0, 0}}
        for _, r := range key {
            nextPaths := make([]path, 0)
            inds := runeInds[r]
            for _, j := range inds {
                minSteps := math.MaxInt64
                for _, p := range prevPaths {
                    diff := abs(p.ind - j)
                    s := p.steps + min(diff+ 1, n - diff + 1)
                    if s < minSteps {
                        minSteps = s
                        bestPath = path{s, j}
                    }
                }
                nextPaths = append(nextPaths, bestPath)
            }
            prevPaths = nextPaths
        }
        
        // find best path in prevPaths
        minSteps := math.MaxInt64
        for _, p := range prevPaths {
            minSteps = min(p.steps, minSteps)
        }
        return minSteps
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.