为了大包拒了Google,为亚麻当一次渣男!
近日亚麻不但爆出永久WFH的消息
更有接到狗家offer的小伙伴向领扣🐱反馈
亚麻捞人不择手段,薪资怒涨20%
让他忍不住想为了亚麻当一次渣男!
LintCode 1592
查找和替换模式
题目描述
你有一个单词列表 words 和一个模式 pattern,你想知道 words 中的哪些单词与模式匹配。
如果存在字母的排列 p ,使得将模式中的每个字母 x 替换为 p(x) 之后,我们就得到了所需的单词,那么单词与模式是匹配的。
(回想一下,字母的排列是从字母到字母的双射:每个字母映射到另一个字母,没有两个字母映射到同一个字母。)
返回 words 中与给定模式匹配的单词列表。
你可以按任何顺序返回答案。
- 1<=words.length<=50
- 1<=pattern.length=words[i].length<=20
扫码免费做题
↓↓↓
样例1:
输入:words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出:["aqq","mee"]
解释:
"mee" 与模式匹配,因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配,因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。输入:words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出:["aqq","mee"]
解释:
"mee" 与模式匹配,因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配,因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。
样例2:
输入: words = ["a","b","c"], pattern = "a"
输出: ["a","b","c"]
解释:
所有的字符串都匹配。
解题思路
遍历words,逐个匹配是否满足pattern,在匹配时,借助HashMap建立字符映射关系,条件是:每个字母映射到另一个字母中,没有两个字母映射到同一个字母
源代码
publicclassSolution {
/**
* @param words: word list
* @param pattern: pattern string
* @return: list of matching words
*/
public List<String> findAndReplacePattern(String[] words, String pattern) {
// Write your code here.
int[] p = F(pattern);
List<String> res = new ArrayList<String>();
for (String w : words)
if (Arrays.equals(F(w), p)) res.add(w);
return res;
}
publicint[] F(String w) {
HashMap<Character, Integer> m = new HashMap<>();
int n = w.length();
int[] res = newint[n];
for (int i = 0; i < n; i++) {
m.putIfAbsent(w.charAt(i), m.size());
res[i] = m.get(w.charAt(i));
}
return res;
}
}
点击【阅读原文】,查看领扣原题。
阅读原文 关键词
单词
亚麻
字母映射到
与模式
映射到同一个字母
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。