func palindromePairs(words []string) (res [][]int) {
	m := make(map[string]int)
	n := len(words)
	for i := 0; i < n; i++ {
		k := len(words[i])
		runes := make([]rune, k)
		for _, r := range words[i] {
			k--
			runes[k] = r
		}
		m[string(runes)] = i
	}
	for i := 0; i < n; i++ {
		if idx, ok := m[""]; ok && idx != i && isPalindrome(words[i]) {
			res = append(res, []int{idx, i}) // Empty string and palindrome
			res = append(res, []int{i, idx})
		}
		if idx, ok := m[words[i]]; ok && idx != i {
			res = append(res, []int{idx, i}) // Whole string and its reverse
		}
		k := len(words[i])
		for j := 1; j < k; j++ {
			wl, wr := words[i][:j], words[i][j:]
			if idx, ok := m[wr]; ok && isPalindrome(wl) { // wr' + wl + wr
				res = append(res, []int{idx, i})
			}
			if idx, ok := m[wl]; ok && isPalindrome(wr) { // wl + wr + wl'
				res = append(res, []int{i, idx})
			}
		}
	}
	return
}

func isPalindrome(s string) bool {
	n := len(s)
	for l, r := 0, n-1; l < r; l, r = l+1, r-1 {
		if s[l] != s[r] {
			return false
		}
	}
	return true
}

func palindromePairsOn3(words []string) (res [][]int) { // Brute search, O(n^3)
	n := len(words)
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			b1, b2 := isPalindromePair(words[i], words[j])
			if b1 {
				res = append(res, []int{i, j})
			}
			if b2 {
				res = append(res, []int{j, i})
			}
		}
	}
	return
}

func isPalindromePair(s1, s2 string) (bool, bool) {
	s12, s21 := s1+s2, s2+s1
	n := len(s12)
	b1, b2 := true, true
	for l, r := 0, n-1; l < r && (b1 || b2); l, r = l+1, r-1 {
		if s12[l] != s12[r] {
			b1 = false
		}
		if s21[l] != s21[r] {
			b2 = false
		}
	}
	return b1, b2
}