2306. 公司命名

题目描述

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

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

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

示例 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⁴
1 <= ideas[i].length <= 10
ideas[i] 由小写英文字母组成
ideas 中的所有字符串 互不相同

解法

方法一：枚举计数

我们定义 \(f[i][j]\) 表示 \(\textit{ideas}\) 中以第 \(i\) 个字母开头，替换为第 \(j\) 个字母后，不在 \(\textit{ideas}\) 中的字符串的个数。初始时 \(f[i][j] = 0\)。另外，用一个哈希表 \(s\) 记录 \(\textit{ideas}\) 中的字符串，方便我们快速判断某个字符串是否在 \(\textit{ideas}\) 中。

接下来，我们遍历 \(\textit{ideas}\) 中字符串，对于当前遍历到的字符串 \(v\)，我们枚举替换后的第一个字母 \(j\)，如果 \(v\) 替换后的字符串不在 \(\textit{ideas}\) 中，那么我们就更新 \(f[i][j] = f[i][j] + 1\)。

最后，我们再次遍历 \(\textit{ideas}\) 中字符串，对于当前遍历到的字符串 \(v\)，我们枚举替换后的第一个字母 \(j\)，如果 \(v\) 替换后的字符串不在 \(\textit{ideas}\) 中，那么我们就更新答案 \(\textit{ans} = \textit{ans} + f[j][i]\)。

最终答案即为 \(\textit{ans}\)。

时间复杂度 \(O(n \times m \times |\Sigma|)\)，空间复杂度 \(O(|\Sigma|^2)\)。其中 \(n\) 和 \(m\) 分别是 \(\textit{ideas}\) 中字符串的个数和字符串的最大长度，而 \(|\Sigma|\) 是字符串中出现的字符集，本题中 \(|\Sigma| \leq 26\)。

Python3JavaC++Go

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        s = set(ideas)
        f = [[0] * 26 for _ in range(26)]
        for v in ideas:
            i = ord(v[0]) - ord('a')
            t = list(v)
            for j in range(26):
                t[0] = chr(ord('a') + j)
                if ''.join(t) not in s:
                    f[i][j] += 1
        ans = 0
        for v in ideas:
            i = ord(v[0]) - ord('a')
            t = list(v)
            for j in range(26):
                t[0] = chr(ord('a') + j)
                if ''.join(t) not in s:
                    ans += f[j][i]
        return ans

class Solution {
    public long distinctNames(String[] ideas) {
        Set<String> s = new HashSet<>();
        for (String v : ideas) {
            s.add(v);
        }
        int[][] f = new int[26][26];
        for (String v : ideas) {
            char[] t = v.toCharArray();
            int i = t[0] - 'a';
            for (int j = 0; j < 26; ++j) {
                t[0] = (char) (j + 'a');
                if (!s.contains(String.valueOf(t))) {
                    ++f[i][j];
                }
            }
        }
        long ans = 0;
        for (String v : ideas) {
            char[] t = v.toCharArray();
            int i = t[0] - 'a';
            for (int j = 0; j < 26; ++j) {
                t[0] = (char) (j + 'a');
                if (!s.contains(String.valueOf(t))) {
                    ans += f[j][i];
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_set<string> s(ideas.begin(), ideas.end());
        int f[26][26]{};
        for (auto v : ideas) {
            int i = v[0] - 'a';
            for (int j = 0; j < 26; ++j) {
                v[0] = j + 'a';
                if (!s.count(v)) {
                    ++f[i][j];
                }
            }
        }
        long long ans = 0;
        for (auto& v : ideas) {
            int i = v[0] - 'a';
            for (int j = 0; j < 26; ++j) {
                v[0] = j + 'a';
                if (!s.count(v)) {
                    ans += f[j][i];
                }
            }
        }
        return ans;
    }
};

func distinctNames(ideas []string) (ans int64) {
    s := map[string]bool{}
    for _, v := range ideas {
        s[v] = true
    }
    f := [26][26]int{}
    for _, v := range ideas {
        i := int(v[0] - 'a')
        t := []byte(v)
        for j := 0; j < 26; j++ {
            t[0] = 'a' + byte(j)
            if !s[string(t)] {
                f[i][j]++
            }
        }
    }

    for _, v := range ideas {
        i := int(v[0] - 'a')
        t := []byte(v)
        for j := 0; j < 26; j++ {
            t[0] = 'a' + byte(j)
            if !s[string(t)] {
                ans += int64(f[j][i])
            }
        }
    }
    return
}

2306. 公司命名

题目描述

解法

方法一：枚举计数

评论