題目

給你一個數組 favoriteCompanies ，

其中 favoriteCompanies[i] 是第 i 名使用者收藏的公司清單（下標從 0 開始）。

請找出不是其他任何人收藏的公司清單的子集的收藏清單，並返回該清單下標。下標需要按升序排列。

示例 1：輸入：favoriteCompanies = [["leetcode","google","facebook"],

["google","microsoft"],["google","facebook"],["google"],["amazon"]]

輸出：[0,1,4]

解釋：favoriteCompanies[2]=["google","facebook"] 是

favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。

favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=

["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。

其餘的收藏清單均不是其他任何人收藏的公司清單的子集，因此，答案為 [0,1,4] 。

示例 2：輸入：favoriteCompanies = [["leetcode","google","facebook"],

["leetcode","amazon"],["facebook","google"]]

輸出：[0,1]

解釋：favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集，因此，答案為 [0,1] 。

示例 3：輸入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]

輸出：[0,1,2,3]

提示：1 <= favoriteCompanies.length <= 100

1 <= favoriteCompanies[i].length <= 500

1 <= favoriteCompanies[i][j].length <= 20

favoriteCompanies[i] 中的所有字串 各不相同 。

使用者收藏的公司清單也 各不相同 ，

也就是說，即便我們按字母順序排序每個清單， favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。

所有字串僅包含小寫英文字母。

解題思路分析

1、自定義排序；時間複雜度O(n^3)，空間複雜度O(n^2)

type Node struct {	index int	str   []string}func peopleIndexes(favoriteCompanies [][]string) []int {	n := len(favoriteCompanies)	arr := make([]Node, 0)	for i := 0; i < n; i++ {		arr = append(arr, Node{			index: i,			str:   favoriteCompanies[i],		})	}	sort.Slice(arr, func(i, j int) bool {		return len(arr[i].str) < len(arr[j].str)	})	res := make([]int, 0)	for i := 0; i < n; i++ {		flag := true		for j := i + 1; j < n; j++ {			if judge(arr[i].str, arr[j].str) == true {				flag = false				break			}		}		if flag == true {			res = append(res, arr[i].index)		}	}	sort.Ints(res)	return res}func judge(a, b []string) bool {	m := make(map[string]bool)	for i := 0; i < len(a); i++ {		m[a[i]] = true	}	for i := 0; i < len(b); i++ {		if _, ok := m[b[i]]; ok {			delete(m, b[i])		}	}	return len(m) == 0}

總結

Medium題目，暴力法容易超時，先根據長度排序後再比較即可