Question

2306. 公司命名

English Version

题目描述

给你一个字符串数组 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 * 104
• 1 <= ideas[i].length <= 10
• ideas[i] 由小写英文字母组成
• ideas 中的所有字符串 互不相同

解法

方法一：枚举计数

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

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

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

最终答案即为 $ans$。

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

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
}

function distinctNames(ideas: string[]): number {
  const s = new Set(ideas);
  const f: number[][] = Array(26)
    .fill(0)
    .map(() => Array(26).fill(0));
  for (const v of s) {
    const i = v.charCodeAt(0) - 'a'.charCodeAt(0);
    const t = [...v];
    for (let j = 0; j < 26; ++j) {
      t[0] = String.fromCharCode('a'.charCodeAt(0) + j);
      if (!s.has(t.join(''))) {
        f[i][j]++;
      }
    }
  }
  let ans = 0;
  for (const v of s) {
    const i = v.charCodeAt(0) - 'a'.charCodeAt(0);
    const t = [...v];
    for (let j = 0; j < 26; ++j) {
      t[0] = String.fromCharCode('a'.charCodeAt(0) + j);
      if (!s.has(t.join(''))) {
        ans += f[j][i];
      }
    }
  }
  return ans;
}