Skip to content

Latest commit

 

History

History
218 lines (179 loc) · 6.73 KB

README.md

File metadata and controls

218 lines (179 loc) · 6.73 KB
comments difficulty edit_url rating source tags
true
中等
1828
第 275 场周赛 Q3
位运算
数组
哈希表
字符串
排序

2135. 统计追加字母可以获得的单词数

English Version

题目描述

给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。

对于 targetWords 中的每个字符串，检查是否能够从 startWords 中选出一个字符串，执行一次 转换操作 ，得到的结果与当前 targetWords 字符串相等。

转换操作 如下面两步所述：

  1. 追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。 
    <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 * 104
  • 1 <= startWords[i].length, targetWords[j].length <= 26
  • startWords 和 targetWords 中的每个字符串都仅由小写英文字母组成
  • 在 startWords 或 targetWords 的任一字符串中，每个字母至多出现一次

解法

方法一

Python3

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        s = set()
        for word in startWords:
            mask = 0
            for c in word:
                mask |= 1 << (ord(c) - ord('a'))
            s.add(mask)

        ans = 0
        for word in targetWords:
            mask = 0
            for c in word:
                mask |= 1 << (ord(c) - ord('a'))
            for c in word:
                t = mask ^ (1 << (ord(c) - ord('a')))
                if t in s:
                    ans += 1
                    break
        return ans

Java

class Solution {

    public int wordCount(String[] startWords, String[] targetWords) {
        Set<Integer> s = new HashSet<>();
        for (String word : startWords) {
            int mask = 0;
            for (char c : word.toCharArray()) {
                mask |= (1 << (c - 'a'));
            }
            s.add(mask);
        }
        int ans = 0;
        for (String word : targetWords) {
            int mask = 0;
            for (char c : word.toCharArray()) {
                mask |= (1 << (c - 'a'));
            }
            for (char c : word.toCharArray()) {
                int t = mask ^ (1 << (c - 'a'));
                if (s.contains(t)) {
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        unordered_set<int> s;
        for (auto& word : startWords) {
            int mask = 0;
            for (char c : word)
                mask |= (1 << (c - 'a'));
            s.insert(mask);
        }
        int ans = 0;
        for (auto& word : targetWords) {
            int mask = 0;
            for (char c : word)
                mask |= (1 << (c - 'a'));
            for (char c : word) {
                int t = mask ^ (1 << (c - 'a'));
                if (s.count(t)) {
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
};

Go

func wordCount(startWords []string, targetWords []string) int {
	s := make(map[int]bool)
	for _, word := range startWords {
		mask := 0
		for _, c := range word {
			mask |= (1 << (c - 'a'))
		}
		s[mask] = true
	}
	ans := 0
	for _, word := range targetWords {
		mask := 0
		for _, c := range word {
			mask |= (1 << (c - 'a'))
		}
		for _, c := range word {
			t := mask ^ (1 << (c - 'a'))
			if s[t] {
				ans++
				break
			}
		}
	}
	return ans
}