findperm.go

package main

// You are given a string, s, and a list of words, words, that are all of the same length.
// Find all starting indices of substring(s) in s that is a concatenation of each word
// in words exactly once and without any intervening characters.
// s := "barfoothefoobarman"
// words := [2]string{"foo", "bar"}
// Output: [0,9]

func main() {
	s := "barfoothefoobarman"
	words := []string{"foo", "bar", "poo"}
	findSubstring(s, words)
}

func permuteHelper(words []string, current string, out *[]string) {
	if len(words) == 0 {
		*out = append(*out, current)
		return
	}

	for i := 0; i < len(words); i++ {
		word := words[i]
		current += word
		newWords := make([]string, len(words))
		copy(newWords, words)
		newWords = append(newWords[:i], newWords[i+1:]...)
		permuteHelper(newWords, current, out)
		current = current[:len(current)-len(words[i])]
	}

	return
}

func getCombinations(words []string) []string {
	var out []string
	current := ""
	permuteHelper(words, current, &out)
	return out
}

func findSubstring(s string, words []string) []int {
	// ret := []string{}
	// fmt.Println(words)
	getCombinations(words)
	// word := strings.Join(words, "")
	// ss := strings.Index(s, word)
	// fmt.Println(ret)
	// return ret

	return []int{}
}