博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
890. Find and Replace Pattern找出匹配形式的单词
阅读量:5156 次
发布时间:2019-06-13

本文共 2470 字,大约阅读时间需要 8 分钟。

[抄题]:

You have a list of words and a pattern, and you want to know which words in words matches the pattern.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)

Return a list of the words in words that match the given pattern. 

You may return the answer in any order.

 

Example 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"Output: ["mee","aqq"]Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. "ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,since a and b map to the same letter.

 [暴力解法]:

时间分析:

空间分析:

 [优化后]:

时间分析:

空间分析:

[奇葩输出条件]:

[奇葩corner case]:

[思维问题]:

以为要像处理["abc","bcd","xyz"]一样,累计diff = string.charAt(i) - string.charAt(i - 1);

但是这道题其实和总偏移量没啥关系,abb aqq acc都可以。所以要用匹配

[英文数据结构或算法,为什么不用别的数据结构或算法]:

[一句话思路]:

s[w.charAt(i)-'a']=p[pattern.charAt(i)-'a']=i+1;一次匹配一对,没匹配上不行

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

[一刷]:

控制真假的boolean变量,在计算每个单词之前,要恢复成true的初始状态

[二刷]:

[三刷]:

[四刷]:

[五刷]:

  [五分钟肉眼debug的结果]:

[总结]:

s[0] = p[9] = 相同的位置坐标,一次匹配一对

[复杂度]:Time complexity: O(n2) Space complexity: O(n)

[算法思想:迭代/递归/分治/贪心]:

[关键模板化代码]:

[其他解法]:

[Follow Up]:

[LC给出的题目变变变]:

 [代码风格] :

 [是否头一次写此类driver funcion的代码] :

 [潜台词] :

 

class Solution {    public List
findAndReplacePattern(String[] words, String pattern) { //initialiazation List
result = new ArrayList
(); //for loop for each word for (String word : words) { boolean match = true; int[] w = new int[26]; int[] p = new int[26]; //for loop for each char for (int i = 0; i < word.length(); i++) { if (w[word.charAt(i) - 'a'] != p[pattern.charAt(i) - 'a']) { match = false; break; } if (match == true) { w[word.charAt(i) - 'a'] = i + 1; p[pattern.charAt(i) - 'a'] = i + 1; } } if (match == true) result.add(word); } //return return result; }}
View Code

 

转载于:https://www.cnblogs.com/immiao0319/p/9595929.html

你可能感兴趣的文章
通过 poi 导入 Excel代码
查看>>
《CSS基础教程》 读书笔记三
查看>>
洛谷P4482 [BJWC2018]Border 的四种求法 字符串,SAM,线段树合并,线段树,树链剖分,DSU on Tree...
查看>>
PHP安全新闻早8点_1127
查看>>
57.Insert Interval
查看>>
PHP 五大运行模式
查看>>
CSS选项卡
查看>>
HDOJ1203 I NEED A OFFER!
查看>>
ZH奶酪:自然语言处理工具LTP语言云调用方法
查看>>
.NET中将图片文件流转成Base64字符串的实现
查看>>
js如何操作或是更改sass里的变量
查看>>
BZOJ1419: Red is good
查看>>
POJ 3308 Paratroopers (对数转换+最小点权覆盖)
查看>>
rendering omni shadow in one pass.
查看>>
No repository found containing,eclipse 自动更新erro 解决
查看>>
iOS设计模式之单例模式
查看>>
MySQL面试题中:主从同步的原理
查看>>
HTTP和WebSocket协议(二)
查看>>
项目练习(二)—微博数据结构化
查看>>
尤金·卡巴斯基:卡巴斯基实验室调查内网遭黑客攻击事件
查看>>