搜索
首页Javajava教程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) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch3str = 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) != &#39; &#39;) {
                j++;
            }
            String tmp = str.substring(i, j);
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
                return false;
            }
            if (ch3str.containsKey(ch) && !tmp.equals(ch3str.get(ch))) {
                return false;
            }
            str2ch.put(tmp, ch);
            ch3str.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算法之单词规律问题怎么解决的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:亿速云。如有侵权,请联系admin@php.cn删除
Go语言如何实现国密SM4和SM2算法的加解密以及互联互通?Go语言如何实现国密SM4和SM2算法的加解密以及互联互通?Apr 19, 2025 pm 06:27 PM

Go语言实现国密SM4和SM2加解密本文将详细介绍如何使用Go语言实现国密SM4和SM2算法的加解密流程,以满足与Java应�...

在Python项目中是否需要进行分层?在Python项目中是否需要进行分层?Apr 19, 2025 pm 06:24 PM

在Python项目中是否需要分层?最近我在学习Python时,注意到Django开源项目中,很多都在views函数里编写了大量的�...

如何使用MapStruct简化系统对接中的字段映射问题?如何使用MapStruct简化系统对接中的字段映射问题?Apr 19, 2025 pm 06:21 PM

系统对接中的字段映射处理在进行系统对接时,常常会遇到一个棘手的问题:如何将A系统的接口字段有效地映�...

IntelliJ IDEA是如何通过JavaAgent和RMI技术识别Spring Boot项目的端口号的?IntelliJ IDEA是如何通过JavaAgent和RMI技术识别Spring Boot项目的端口号的?Apr 19, 2025 pm 06:18 PM

IntelliJIDEA如何识别SpringBoot项目的端口号?在使用IntelliJIDEAUltimate版本启动Spring...

高效编程:如何才能找到可靠的代码工具和资源?高效编程:如何才能找到可靠的代码工具和资源?Apr 19, 2025 pm 06:15 PM

高效编程:寻找可靠的代码工具和资源很多程序员都渴望找到便捷的代码工具网站,以提高效率,避免在海量信...

JWT能否实现动态权限变更?与Session机制有何区别?JWT能否实现动态权限变更?与Session机制有何区别?Apr 19, 2025 pm 06:12 PM

关于JWT和Session的困惑与解答许多初学者在学习JWT和Session时,常常会对其本质和适用场景感到困惑。本文将围绕J...

Windows Server 2019防火墙如何正确配置才能支持WebSocket通信?Windows Server 2019防火墙如何正确配置才能支持WebSocket通信?Apr 19, 2025 pm 06:09 PM

WindowsServer2019防火墙与WebSocket通信问题详解在使用SpringBoot开发的Jar程序部署于WindowsServer2019...

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境