文档章节

LeetCode:Word Pattern - 字符串模式匹配

北风其凉
 北风其凉
发布于 2015/10/09 21:59
字数 600
阅读 2371
收藏 1

1、题目名称

Word Pattern(字符串模式匹配)

2、题目地址

https://leetcode.com/problems/word-pattern/

3、题目内容

英文:Given a pattern and a string str, find if str follows the same pattern.

中文:给出一组模式(pattern)和一个字符串(str),查看字符串是否与模式匹配

例如:

  1. pattern = "abba",str = "dog cat cat dog",返回真

  2. pattern = "abba",str = "dog cat cat fish",返回假

  3. pattern = "aaaa",str = "dog cat cat dog",返回假

  4. pattern = "abba",str = "dog dog dog dog",返回假

注意:

模式仅有小写字母构成,字符串被单个空格字符隔开,字符串中每个单词都由小写字母构成;模式和字符串的前后都不包含多余的空格;模式中的每个字母必须匹配一个字符串中长度至少为1的单词。

4、解题方法1

使用HashMap可以很方便地解决本问题。

需要注意的是,模式中的两个不同的字符,不能对应字符串中相同的单词。

Java代码如下:

import java.util.HashMap;

/**
 * @功能说明:LeetCode 290 - Word Pattern
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月9日
 */
public class Solution {
    
    /**
     * 字符串模式匹配
     * @param pattern
     * @param str
     * @return
     */
    public boolean wordPattern(String pattern, String str) {
        
        if (pattern.isEmpty() || str.isEmpty()) {
            return false;
        }
        
        String[] s = str.split(" ");
        if (s.length != pattern.length()) {
            return false;
        }
        
        HashMap<Character, String> hashMap = new HashMap<Character, String>();
        for (int i = 0; i < pattern.length(); i++) {
            if (hashMap.containsKey(pattern.charAt(i))) {
                if (!hashMap.get(pattern.charAt(i)).equals(s[i])) {
                    return false;
                }
            } else if (hashMap.containsValue(s[i])) {
                return false;
            } else {
                hashMap.put(pattern.charAt(i), s[i]);
            }
        }
        
        return true;
    }
}

5、解题方法2

另一个办法需要利用HashMap中put函数的性质。

put函数的声明如下:

public V put(K key, V value)

它的功能是将键值对存入map中,如果map中原本就包含要插入的键,将旧值替换为新值。对于该函数的返回值,如果要插入的键在字典中不存在,则返回null,否则返回替换前的值。根据put函数的性质,可以作出如下Java代码:

import java.util.HashMap;
import java.util.Objects;

/**
 * @功能说明:LeetCode 290 - Word Pattern
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月9日
 */
public class Solution {
    
    /**
     * 模式匹配
     * @param pattern
     * @param str
     * @return
     */
    public boolean wordPattern(String pattern, String str) {
        
        if (pattern.isEmpty() || str.isEmpty()) {
            return false;
        }
        
        String[] s = str.split(" ");
        if (s.length != pattern.length()) {
            return false;
        }
        
        @SuppressWarnings("rawtypes")
        HashMap<Comparable, Integer> hashMap = new HashMap<Comparable, Integer>();
        for (int i = 0; i < pattern.length(); i++) {
            if (!Objects.equals(hashMap.put(pattern.charAt(i), i), hashMap.put(s[i], i)))
                return false;
        }
        
        return true;
    }
}

END

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 114
博文 497
码字总数 462457
作品 4
朝阳
程序员
Linux自学笔记——Bash脚本之数组以及内置字符串处理

数组: 程序=指令+数据 指令:command 数据:变量、文件 变量:存储单个元素的内存空间; 数组:存储多个元素的连续的内存空间; 数组名:整个数组只有一个名字; 数组索引:编号从0开始; ...

claude_liu
2017/09/29
0
0
shell编程(二)

博主名: 李常明 博文地址: http://keep88.blog.51cto.com 此笔记出自老男孩书籍: 跟老男孩学linux运维 shell编程实战 shell变量知识进阶与实践 1、shell中的特殊位置参数变量: 例如: 1)...

咖啡猫Mr
2017/05/31
0
0
python库之re模块

首先:re库中有 all = [ "match", "search", "sub", "subn", "split", "findall", 1.match: 这个函数的意思是从头开始匹配,如果有将匹配上的数据返回,但只返回第一个,如果没有匹配上将返...

邪云
03/10
0
0
Bash编程之数组和字符串处理

Bash编程之数组和字符串处理 目录 笔记日期20180405 数组 声名(创建)数组declare -a ARRAY_NAME 数组元素的赋值ARRAY_NAME=("VAL1" "VAL2" "VAL3"...) 引用数组元素:${ARRAY_NAME[INDEX]} ...

Winthcloud
06/29
0
0
Linux 之 shell 比较运算符

运算符 描述 示例 文件比较运算符 -e filename 如果 filename 存在,则为真 [ -e /var/log/syslog ] -d filename 如果 filename 为目录,则为真 [ -d /tmp/mydir ] -f filename 如果 filena...

晨曦之光
2012/03/02
139
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

函数调用约定 (cdecl stdcall)

函数调用约定 (cdecl stdcall) 在 C 语言里,我们通过阅读函数声明,就知道怎么携带参数去调用函数,也能在函数体定义内使用这些参数。但是 CPU 并不直接完成函数调用的传参操作,这需要人为...

傅易
2分钟前
0
0
Python 核心编程 (全)

浅拷贝和深拷贝 1.浅拷贝:是对于一个对象的顶层拷贝,通俗的理解是:拷贝了引用,并没有拷贝内容。相当于把变量里面指向的一个地址给了另一个变量就是浅拷贝,而没有创建一个新的对象,如a=b...

代码打碟手
5分钟前
0
0
mysql5.7 修改datadir

mysql 的默认存储路径为 /var/lib/mysql ,修改后为 /data/mysql 关闭服务 service mysql stop 复制mysql 数据文件到新的目录 cp -rp /var/lib/mysql /data 查看原目录的权限,如果新目...

hotsmile
21分钟前
0
0
证书安装指引之Tomcat 证书部署

Tomcat 证书部署 0 申请证书 1 获取证书 如果申请证书时有填写私钥密码,下载可获得Tomcat文件夹,其中有密钥库 www.domain.com.jks; 如果没有填写私钥密码,证书下载包的Tomcat文件夹中包括...

吴伟祥
26分钟前
0
0
ConcurrentHashMap1.7和1.8的底层不同实现

1.Hashmap和HashTable在线程安全方面的优劣? Hashmap多线程会导致HashMap的Entry链表形成环形数据结构,一旦形成环形数据结构,Entry的next节点永远不为空,就会产生死循环获取Entry。 Hash...

刘祖鹏
42分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部