Codeforce 890 查找和替换模式

r囧r小猫 2022-04-13 13:42 224阅读 0赞

## 原题目链接：[CodeForce890][] ##

--------------------

## 分类 ##

Codeforce 字符串

--------------------

## 题意 ##

**模式匹配**

你有一个单词列表 `words` 和一个模式 `pattern`，你想知道 `words` 中的哪些单词与模式匹配。

如果存在字母的排列 `p` ，使得将模式中的每个字母 `x` 替换为 `p(x)` 之后，我们就得到了所需的单词，那么单词与模式是匹配的。

--------------------

## 样例输入输出 ##

输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
    输出：["mee","aqq"]
    解释：
    "mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
    "ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
    因为 a 和 b 映射到同一个字母。

--------------------

## 想法 ##

判断是否匹配函数strMatch，由于题目已知单词长度相同，只需判断在相同的位置，两个单词要有相同的相等或者不等关系即可。

--------------------

## 代码 ##

12ms

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/29 */
    class Solution { 
    public:
        bool strMatch(string str, string pattern){ 
            int len = str.length();
            for(int i=0;i < len;i++){ 
                for(int j=i+1;j < len;j++){ 
                    if((str[i] == str[j]) && (pattern[i] != pattern[j])) return false;
                    if((str[i] != str[j]) && (pattern[i] == pattern[j])) return false;
                }
            }
            return true;
        }
        vector<string> findAndReplacePattern(vector<string>& words, string pattern) { 
            vector<string> set;
            for(int i=0;i < words.size();i++){ 
                if(strMatch(words[i], pattern)){ 
                    set.push_back(words[i]);
                }
            }
            return set;
        }
    };

--------------------

[CodeForce890]: https://leetcode-cn.com/problems/find-and-replace-pattern/submissions/