290. Word Pattern 单词匹配模式
[抄题]:
Given a pattern
and a string str
, find if str
follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern
and a non-empty word in str
.
Examples:
- pattern =
"abba"
, str ="dog cat cat dog"
should return true. - pattern =
"abba"
, str ="dog cat cat fish"
should return false. - pattern =
"aaaa"
, str ="dog cat cat dog"
should return false. - pattern =
"abba"
, str ="dog dog dog dog"
should return false.
Notes:
You may assume pattern
contains only lowercase letters, and str
contains lowercase letters separated by a single space.
[暴力解法]:
时间分析:
空间分析:
[优化后]:
时间分析:
空间分析:
[奇葩输出条件]:
[奇葩corner case]:
二者匹配的问题,不是2*2的空不空,而是二者长度是否相等
[思维问题]:
忘了分离单词怎么写了
[一句话思路]:
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
hashmap两次输入的类型不一致,可以不写类型,直接丢掉<>尖括号
[二刷]:
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
hashmap存同样的值,返回值不同
[复杂度]:Time complexity: O(n) Space complexity: O(n)
[英文数据结构或算法,为什么不用别的数据结构或算法]:
hashmap存同样的值,返回值不同:
import java.util.HashMap;
import java.util.Map; public class Test {
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
String p1 = map.put("11", "22");
System.out.println("p1:" + p1); String p2 = map.put("33", "44");
System.out.println("p2:" + p2); String value1 = map.get("11");
System.out.println("value1:" + value1); String p3 = map.put("11", "44");
System.out.println("p3:" + p3); String value2 = map.get("11");
System.out.println("value2:" + value2);
}
} p1:null
p2:null
value1:22
p3:22
value2:44
[关键模板化代码]:
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
291. Word Pattern II 没有空格,回溯法?
[代码风格] :
class Solution {
public boolean wordPattern(String pattern, String str) {
String[] words = str.split(" ");
if (words.length != pattern.length())
return false;
Map index = new HashMap();
for (Integer i=0; i<words.length; ++i)
if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
return false;
return true;
}
}
最新文章
- HTML网页内容转换成字符串(删除从指定字符串到指定字符串)
- 利用Redis cache优化app查询速度实践
- 黑马程序员——JAVA基础之GUI
- JavaScript:下拉列表框的事件处理
- EXEL表格读取 按键精灵
- Color Length
- xcode7 icon图标设置
- PureLayout
- 终于知道如何使Tab控件的不出现白边的方法了
- 芝麻HTTP:批量部署Splash负载集群
- Thread Pools
- python 可迭代对象 迭代器 生成器总结
- 剑指offer——矩形覆盖
- Python 豆瓣源
- Quartz框架多个trigger任务执行出现漏执行的问题分析--转
- Python基础【day01】:PyChram使用技巧总结(六)
- 【hibernate学习杂记】维护关系的一方和不维护关系的一方的区别与联系
- 网站流量分析指标-PV/UV/PR/IP
- Vue动态实现评分效果
- ansible配置文件 ansible.cfg的一点说明
热门文章
- The RK3066/RK30SDK Android 4.2 audio codec has a bug!
- PHP封装返回Ajax字符串和JSON数组
- C# WebApi 配置复杂路由不生效的问题
- PHP提供的数组比较函数总结
- 【java规则引擎】简单规则的rete网络示意图
- 洛谷P4721 【模板】分治 FFT(分治FFT)
- BZOJ2716:[Violet 3]天使玩偶
- 第六篇 VIM你值得拥有!
- Ext.window.Window
- 使用Spring Boot 和Spring Data JPA访问mysql数据库