亲宝软件园·资讯

展开

Go Java算法单词规律

黄丫丫 人气:0

单词规律

给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

输入: pattern = "abba", s = "dog cat cat dog"

输出: true

输入: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) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch2str = new HashMap<Character, String>();
        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)

加载全部内容

相关教程
猜你喜欢
用户评论