目录
单词规律方法一:哈希表(Java)方法一:哈希表(GO)单词规律
给定一种规律 pattern和一个字符串s,判断 s是否遵循相同的规律。
这里的遵循指完全匹配,例如,pattern里的每个字母和字符串s中的每个非空单词之间存在着双向连接的对应规律。
示例1:示例 2:输入: pattern = "abba", s = "dog cat cat dog"
(资料图)
输出: true
示例 3:输入:pattern = "abba", s = "dog cat cat fish"
输出: false
输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false
提示:
1 <= pattern.length <= 300
pattern只包含小写英文字母
1 <= s.length <= 3000
s只包含小写英文字母和" "
s不包含 任何前导或尾随对空格
s中每个单词都被 单个空格 分隔
方法一:哈希表(Java)
在本题中,我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串,任意一个字符串也只被唯一的一个字符对应。在集合论中,这种关系被称为「双射」。
想要解决本题,我们可以利用哈希表记录每一个字符对应的字符串,以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程,不断更新哈希表,如果发生了冲突,则说明给定的输入不满足双射关系。
题目本质上是让我们判断str中的字符是否与pattern中的字符一一对应
也就是说,pattern中相同的字符在str中也应该相同,不同的字符在str中也应该不同
我们可以通过一个字典记录pattern中每个字符第一次出现的位置,即dict[x]=pattern.index(x)。然后我们遍历对pattern中的每个字母,
记i为当前遍历的索引
则dict[pattern[i]]为pattern中字符pattern[i]的上个索引
判断str中两个索引所对应的字母是否相同,若不同则返回False
class Solution { public boolean wordPattern(String pattern, String str) { Mapstr2ch = new HashMap (); Map ch2str = new HashMap (); int m = str.length(); int i = 0; for (int p = 0; p < pattern.length(); ++p) { char ch = pattern.charAt(p); if (i >= m) { return false; } int j = i; while (j < m && str.charAt(j) != " ") { j++; } String tmp = str.substring(i, j); if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) { return false; } if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) { return false; } str2ch.put(tmp, ch); ch2str.put(ch, tmp); i = j + 1; } return i >= m; } }
时间复杂度:O(n+m)
空间复杂度:O(n+m)
方法一:哈希表(GO)
具体的方法思路内容已经在上文中表述,详情请看上文内容
具体方法:
pattern = "abba", 转成0110
str = "dog cat cat dog",转成0110
func wordPattern(pattern string, str string) bool { p := strings.Split(pattern,"") s := strings.Split(str," ") if len(p) != len(s) { return false } pNum,sNum := 0,0 pString,sString := "","" pMap := map[string]int{} sMap := map[string]int{} for _,v := range p { if _,ok := pMap[v];ok{ pString += strconv.Itoa(pMap[v]) }else{ pString += strconv.Itoa(pNum) pMap[v] = pNum pNum++ } } for _,v := range s { if _,ok := sMap[v];ok{ sString += strconv.Itoa(sMap[v]) }else{ sString += strconv.Itoa(sNum) sMap[v] = sNum sNum++ } } if pString == sString { return true } return false }
时间复杂度:O(n+m)
空间复杂度:O(n+m)
以上就是Go Java算法之单词规律示例详解的详细内容,更多关于Go Java算法单词规律的资料请关注脚本之家其它相关文章!
X 关闭
X 关闭
- 1亚马逊开始大规模推广掌纹支付技术 顾客可使用“挥手付”结账
- 2现代和起亚上半年出口20万辆新能源汽车同比增长30.6%
- 3如何让居民5分钟使用到各种设施?沙特“线性城市”来了
- 4AMD实现连续8个季度的增长 季度营收首次突破60亿美元利润更是翻倍
- 5转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 6充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 7好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 8名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?
- 9亚马逊云科技成立量子网络中心致力解决量子计算领域的挑战
- 10京东绿色建材线上平台上线 新增用户70%来自下沉市场