标签： hard

目标

给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：

1. 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
2. 交换 ideaA 和 ideaB 的首字母。
3. 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
4. 否则，不是一个有效的名字。

返回 不同 且有效的公司名字的数目。

示例 1：

输入：ideas = ["coffee","donuts","time","toffee"]
输出：6
解释：下面列出一些有效的选择方案：
- ("coffee", "donuts")：对应的公司名字是 "doffee conuts" 。
- ("donuts", "coffee")：对应的公司名字是 "conuts doffee" 。
- ("donuts", "time")：对应的公司名字是 "tonuts dime" 。
- ("donuts", "toffee")：对应的公司名字是 "tonuts doffee" 。
- ("time", "donuts")：对应的公司名字是 "dime tonuts" 。
- ("toffee", "donuts")：对应的公司名字是 "doffee tonuts" 。
因此，总共有 6 个不同的公司名字。

下面列出一些无效的选择方案：
- ("coffee", "time")：在原数组中存在交换后形成的名字 "toffee" 。
- ("time", "toffee")：在原数组中存在交换后形成的两个名字。
- ("coffee", "toffee")：在原数组中存在交换后形成的两个名字。

示例 2：

输入：ideas = ["lack","back"]
输出：0
解释：不存在有效的选择方案。因此，返回 0 。

说明：

• 2 <= ideas.length <= 5 * 10^4
• 1 <= ideas[i].length <= 10
• ideas[i] 由小写英文字母组成
• ideas 中的所有字符串 互不相同

思路

将收集到的不同的单词放入 ideas 数组，从中选取两个单词，交换其首字母，如果得到的新单词不在 ideas 中，那么这两个单词的排列是有效的公司名，求不重复的有效的公司名数目。

通过观察示例可以发现，首字母相同是不行的，交换后还是原单词。那么可以建立一个长度为26的数组，元素是以该字母开头的单词 列表。可行的方案是选择两个首字母不同的单词，判断另一方首字母列表中的单词是否包含本方单词的后缀。如果双方都不包含，那么这两个单词的 排列 是有效的公司名。否则，包含该后缀的单词与另一方列表的所有组合都是无效的命名，因为交换后必定重复。比如，coffee 与 time、 toffee，后缀 offee 在两个列表中存在，那么coffee 与 t 开头的任意单词交换首字母，得到的 toffee 已经存在，所以 coffee 与所有以 t 开头的单词组合都不合法。同理，toffee 与 c 开头的任意单词交换首字母，得到 coffee 已存在，toffee 与所有以 c 开头的单词组合都不合法。

考虑这个问题，按照上面方法取得的有效的公司名是否会重复？也就是说，选取另一对不同的单词组合，是否会出现交换首字母后的单词不重复，而组成的公司名重复。假设该对单词组成的公司名已存在，那么原来组成该公司名的单词对必定也是从这两个首字母单词列表中选取。说明 ideas 数组中的单词有重复，这与题目条件矛盾。所以，只要是有效的公司名就不会重复。

假设 ideas 中出现的首字母种类个数为 10，首字母相同的单词个数为 5 * 10^3。那么枚举所有组合需要循环 C(10,2) * 25 * 10^6 = 45 * 25 * 10^6 = 1125 * 10^6 次，大约 10^9 肯定超时。

思考暴力枚举的瓶颈在哪？或者说有哪些循环是没必要的？能否遍历一次，保存状态？我们在循环中做的事情就是

1. 判断当前单词的后缀是否在另一首字母单词列表中存在
2. 判断另一首字母单词的后缀是否在当前首字母单词列表中存在

如果我们可以直接得到当前单词与另一首字母列表中可以结合的单词个数，那么就只需要遍历25个其它首字母就可以了。我们可以记录后缀与首字母集合的映射。然后维护一个 cannotCombine[i][j] 数组，表示以i为首字母的单词，与其它以首字母j开头的单词无法组成有效命名的个数，这样，我们在枚举首字母i内的单词时，可以直接用 words[j].size() - cannotCombine[j][i] 即可得到合法的组合数。

代码

/**
 * @date 2024-09-25 10:42
 */
public class DistinctNames2306 {

    public long distinctNames_v1(String[] ideas) {
        long res = 0L;
        int n = ideas.length;
        Map<String, Set<Integer>> suffixToFirstMap = new HashMap<>();
        List<String>[] words = new List[26];
        for (int i = 0; i < n; i++) {
            String idea = ideas[i];
            int first = idea.charAt(0) - 'a';
            if (words[first] == null) {
                words[first] = new ArrayList<>();
            }
            words[first].add(idea);
            String suffix = idea.substring(1);
            suffixToFirstMap.putIfAbsent(suffix, new HashSet<>());
            suffixToFirstMap.get(suffix).add(first);
        }
        int[][] cannotCombine = new int[26][26];
        for (int i = 0; i < 26; i++) {
            if (words[i] == null) {
                continue;
            }
            for (String word : words[i]) {
                String suffix = word.substring(1);
                Set<Integer> set = suffixToFirstMap.get(suffix);
                if (set != null){
                    for (Integer index : set) {
                        cannotCombine[i][index]++;
                    }
                }
            }
        }

        for (int i = 0; i < 26; i++) {
            List<String> iWord = words[i];
            if (iWord == null) {
                continue;
            }
            for (int j = 0; j < iWord.size(); j++) {
                String word = iWord.get(j);
                String suffix = word.substring(1);
                for (int k = i + 1; k < 26; k++) {
                    Set<Integer> set = suffixToFirstMap.get(suffix);
                    if (set != null && words[k] != null && !set.contains(k)) {
                        res += 2 * (words[k].size() - cannotCombine[k][i]);
                    }
                }
            }
        }
        return res;
    }

}

性能