https://leetcode.com/problems/evaluate-division/

calcEquation.go

type void struct{}
type g = map[string](map[string]float64)
type stringSet = map[string]void

var member void

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	// 1. Make a directed, weighted graph out of each equation
	graph, seen := make(g), make(stringSet)
	for i, vars := range equations {
		numerator, denominator := vars[0], vars[1]
		if graph[numerator] == nil {
			graph[numerator] = make(map[string]float64)
		}
		if graph[denominator] == nil {
			graph[denominator] = make(map[string]float64)
		}
		graph[numerator][denominator] = values[i]
		graph[denominator][numerator] = 1 / values[i]
	}

	// 2. Define some way to traverse from one vertex to another in the graph
	var dfs func(string, string) float64
	dfs = func(node, destination string) float64 {
		_, visited := seen[node]
		switch {
		case node == destination:
			return 1
		case visited:
			return -1
		default:
			seen[node] = member
			defer func() { delete(seen, node) }()
			for sister, weight := range graph[node] {
				searchResult := dfs(sister, destination)
				if searchResult != -1 {
					return searchResult * weight
				}
			}
			return -1
		}
	}

	// 3. For each query, traverse to solve the equation
	result := make([]float64, len(queries))
	for i, q := range queries {
		origin, destination := q[0], q[1]
		_, existO := graph[origin]
		_, existD := graph[destination]
		switch {
		case !existO || !existD:
			result[i] = -1
		case origin == destination:
			result[i] = 1
		default:
			result[i] = dfs(origin, destination)
		}
	}

	return result
}