[Google] LeetCode 2135 Count Words Obtained After Adding a Letter

本文主要是介绍[Google] LeetCode 2135 Count Words Obtained After Adding a Letter，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only.

For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords.

The conversion operation is described in the following two steps:

• Append any lowercase letter that is not present in the string to its end.
  For example, if the string is "abc", the letters 'd', 'e', or 'y' can be added to it, but not 'a'. If 'd' is added, the resulting string will be "abcd".
• Rearrange the letters of the new string in any arbitrary order.
  For example, "abcd" can be rearranged to "acbd", "bacd", "cbda", and so on. Note that it can also be rearranged to "abcd" itself.

Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.

Solution

由于可以进行 \(rearrange\)，所以我们只需要用 \(sort\) 即可。然后用 \(map\) 来查找即可

class Solution {
private:
    unordered_set<string> s;
    int ans=0;
    
public:
    int wordCount(vector<string>& sw, vector<string>& tw) {
        int n = sw.size(), m = tw.size();
        for(int i=0;i<n;i++){
            sort(sw[i].begin(), sw[i].end());
            s.insert(sw[i]);
        }
        for(int i=0;i<m;i++){
            string cur = tw[i];
            sort(cur.begin(), cur.end());
            for(int j=0;j<tw[i].size();j++){
                string tmp=cur;
                tmp.erase(tmp.begin()+j);
                if(s.find(tmp)!=s.end()){ans++;break;}
            }
        }
        return ans;
    }
};

这篇关于[Google] LeetCode 2135 Count Words Obtained After Adding a Letter的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！