这篇文章主要为大家介绍了Go Java算法之单词规律示例详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
单词规律
给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
- 示例1:
输入: pattern = "abba", s = "dog cat cat dog"
输出: true
- 示例 2:
输入:pattern = "abba", s = "dog cat cat fish"
输出: false
- 示例 3:
输入: 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 = m) { return false; } int j = i; while (j = 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算法单词规律的资料请关注0133技术站其它相关文章!
以上就是Go Java算法之单词规律示例详解的详细内容,更多请关注0133技术站其它相关文章!