| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1828 |
第 275 场周赛 Q3 |
|
给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。
对于 targetWords 中的每个字符串，检查是否能够从 startWords 中选出一个字符串，执行一次 转换操作 ，得到的结果与当前 targetWords 字符串相等。
转换操作 如下面两步所述：
- 追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。
<ul> <li>例如，如果字符串为 <code>"abc"</code> ，那么字母 <code>'d'</code>、<code>'e'</code> 或 <code>'y'</code> 都可以加到该字符串末尾，但 <code>'a'</code> 就不行。如果追加的是 <code>'d'</code> ，那么结果字符串为 <code>"abcd"</code> 。</li> </ul> </li> <li><strong>重排</strong> 新字符串中的字母，可以按 <strong>任意</strong> 顺序重新排布字母。 <ul> <li>例如，<code>"abcd"</code> 可以重排为 <code>"acbd"</code>、<code>"bacd"</code>、<code>"cbda"</code>，以此类推。注意，它也可以重排为 <code>"abcd"</code> 自身。</li> </ul> </li>
找出 targetWords 中有多少字符串能够由 startWords 中的 任一 字符串执行上述转换操作获得。返回 targetWords 中这类 字符串的数目 。
注意：你仅能验证 targetWords 中的字符串是否可以由 startWords 中的某个字符串经执行操作获得。startWords 中的字符串在这一过程中 不 发生实际变更。
示例 1：
输入：startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"] 输出：2 解释： - 为了形成 targetWords[0] = "tack" ，可以选用 startWords[1] = "act" ，追加字母 'k' ，并重排 "actk" 为 "tack" 。 - startWords 中不存在可以用于获得 targetWords[1] = "act" 的字符串。 注意 "act" 确实存在于 startWords ，但是 必须 在重排前给这个字符串追加一个字母。 - 为了形成 targetWords[2] = "acti" ，可以选用 startWords[1] = "act" ，追加字母 'i' ，并重排 "acti" 为 "acti" 自身。
示例 2：
输入：startWords = ["ab","a"], targetWords = ["abc","abcd"] 输出：1 解释： - 为了形成 targetWords[0] = "abc" ，可以选用 startWords[0] = "ab" ，追加字母 'c' ，并重排为 "abc" 。 - startWords 中不存在可以用于获得 targetWords[1] = "abcd" 的字符串。
提示：
1 <= startWords.length, targetWords.length <= 5 * 1041 <= startWords[i].length, targetWords[j].length <= 26startWords和targetWords中的每个字符串都仅由小写英文字母组成- 在
startWords或targetWords的任一字符串中，每个字母至多出现一次
我们注意到，题目中给定的字符串只包含小写字母，并且每个字符串的字母至多出现一次。因此，我们可以用一个长度为
我们可以将字符串数组
时间复杂度
class Solution:
def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
s = {sum(1 << (ord(c) - 97) for c in w) for w in startWords}
ans = 0
for w in targetWords:
x = sum(1 << (ord(c) - 97) for c in w)
for c in w:
if x ^ (1 << (ord(c) - 97)) in s:
ans += 1
break
return ansclass Solution {
public int wordCount(String[] startWords, String[] targetWords) {
Set<Integer> s = new HashSet<>();
for (var w : startWords) {
int x = 0;
for (var c : w.toCharArray()) {
x |= 1 << (c - 'a');
}
s.add(x);
}
int ans = 0;
for (var w : targetWords) {
int x = 0;
for (var c : w.toCharArray()) {
x |= 1 << (c - 'a');
}
for (var c : w.toCharArray()) {
if (s.contains(x ^ (1 << (c - 'a')))) {
++ans;
break;
}
}
}
return ans;
}
}class Solution {
public:
int wordCount(vector<string>& startWords, vector<string>& targetWords) {
unordered_set<int> s;
for (auto& w : startWords) {
int x = 0;
for (char c : w) {
x |= 1 << (c - 'a');
}
s.insert(x);
}
int ans = 0;
for (auto& w : targetWords) {
int x = 0;
for (char c : w) {
x |= 1 << (c - 'a');
}
for (char c : w) {
if (s.contains(x ^ (1 << (c - 'a')))) {
++ans;
break;
}
}
}
return ans;
}
};func wordCount(startWords []string, targetWords []string) (ans int) {
s := map[int]bool{}
for _, w := range startWords {
x := 0
for _, c := range w {
x |= 1 << (c - 'a')
}
s[x] = true
}
for _, w := range targetWords {
x := 0
for _, c := range w {
x |= 1 << (c - 'a')
}
for _, c := range w {
if s[x^(1<<(c-'a'))] {
ans++
break
}
}
}
return
}function wordCount(startWords: string[], targetWords: string[]): number {
const s = new Set<number>();
for (const w of startWords) {
let x = 0;
for (const c of w) {
x ^= 1 << (c.charCodeAt(0) - 97);
}
s.add(x);
}
let ans = 0;
for (const w of targetWords) {
let x = 0;
for (const c of w) {
x ^= 1 << (c.charCodeAt(0) - 97);
}
for (const c of w) {
if (s.has(x ^ (1 << (c.charCodeAt(0) - 97)))) {
++ans;
break;
}
}
}
return ans;
}