[Leetcode] Word Pattern 单词模式

wdzgege 发布于2019-08-14 12:43 / 3401人阅读

摘要：哈希表法复杂度时间空间思路这题几乎和一模一样，不同的就是之前是字母映射字母，现在是字母映射字符串而已。

Word Pattern

Given a pattern and a string str, find if str follows the same pattern.
Examples: 
pattern = "abba", str = "dog cat cat dog" should return true. 
pattern = "abba", str = "dog cat cat fish" should return false. 
pattern = "aaaa", str = "dog cat cat dog" should return false. 
pattern = "abba", str = "dog dog dog dog" should return false. 
Notes: patterncontains only lowercase alphabetical letters, and str contains words separated by a single space. Each word in str contains only lowercase alphabetical letters. Both pattern and str do not have leading or trailing spaces. Each letter in pattern must map to a word with length that is at least 1.

哈希表法 复杂度

时间 O(N) 空间 O(N)

思路

这题几乎和Isomorphic Strings一模一样，不同的就是之前是字母映射字母，现在是字母映射字符串而已。

代码

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map map = new HashMap();
        Set set = new HashSet();
        String[] pieces = str.split(" ");
        if(pieces.length != pattern.length()) return false;
        int i = 0;
        for(String s : pieces){
            char p = pattern.charAt(i);
            System.out.println(p);
            // 如果该字符产生过映射
            if(map.containsKey(p)){
                // 且映射的字符串和当前字符串不一样
                if(!s.equals(map.get(p))) return false;
            } else {
            // 如果该字符没有产生过映射
                // 如果当前字符串已经被映射过了
                if(set.contains(s)) return false;
                // 否则新加一组映射
                map.put(p, s);
                set.add(s);
            }
            i++;
        }
        return true;
    }
}

Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Examples: pattern = "abab", str = "redblueredblue" should return true. pattern = "aaaa", str = "asdasdasdasd" should return true. pattern = "aabb", str = "xyzabcxzyabc" should return false. Notes: You may assume both pattern and str contains only lowercase letters.

回溯法 复杂度

时间 O(N) 空间 O(N)

思路

因为目标字符串可以任意划分，所以我们不得不尝试所有可能性。这里通过深度优先搜索的回溯法，对于pattern中每个字母，在str中尝试所有的划分方式，如果划分出来的子串可以用这个字母映射，或者可以建立一个新的字母和字符串的映射关系，我们就继续递归判断下一个pattern中的字母。

代码

public class Solution {
    
    Map map;
    Set set;
    boolean res;
    
    public boolean wordPatternMatch(String pattern, String str) {
        // 和I中一样，Map用来记录字符和字符串的映射关系
        map = new HashMap();
        // Set用来记录哪些字符串被映射了，防止多对一映射
        set = new HashSet();
        res = false;
        // 递归回溯
        helper(pattern, str, 0, 0);
        return res;
    }
    
    public void helper(String pattern, String str, int i, int j){
        // 如果pattern匹配完了而且str也正好匹配完了，说明有解
        if(i == pattern.length() && j == str.length()){
            res = true;
            return;
        }
        // 如果某个匹配超界了，则结束递归
        if(i >= pattern.length() || j >= str.length()){
            return;
        }
        char c = pattern.charAt(i);
        // 尝试从当前位置到结尾的所有划分方式
        for(int cut = j + 1; cut <= str.length(); cut++){
            // 拆出一个子串
            String substr = str.substring(j, cut);
            // 如果这个子串没有被映射过，而且当前pattern的字符也没有产生过映射
            // 则新建一对映射，并且继续递归求解
            if(!set.contains(substr) && !map.containsKey(c)){
                map.put(c, substr);
                set.add(substr);
                helper(pattern, str, i + 1, cut);
                map.remove(c);
                set.remove(substr);
            // 如果已经有映射了，但是是匹配的，也继续求解
            } else if(map.containsKey(c) && map.get(c).equals(substr)){
                helper(pattern, str, i + 1, cut);
            }
            // 否则跳过该子串，尝试下一种拆分
        }
    }
}

云服务器 GPU云服务器 Pattern LeetCode LeetCode_String design-pattern

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64664.html

890-查找和替换模式

摘要：前言的的题目查找和替换模式，原题目描述如下你有一个单词列表和一个模式，你想知道中的哪些单词与模式匹配。如果存在字母的排列，使得将模式中的每个字母替换为之后，我们就得到了所需的单词，那么单词与模式是匹配的。前言 LeetCode的Weekly Contest 98的题目查找和替换模式，原题目描述如下：你有一个单词列表 words 和一个模式 pattern，你想知道 words 中...

haobowd 2019-08-19 10:59 评论0 收藏0
LeetCode 290 单词模式 JS实现

摘要：给定一种模式和一个字符串，判断是否遵循相同的模式。这里的遵循指完全匹配，例如，里的每个字母和字符串中的每个非空单词之间存在着双向连接的对应模式。示例输入输出示例输入输出说明你可以假设只包含小写字母，包含了由单个空格分隔的小写字母。给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。这里的遵循指完全匹配，例如， pattern 里的每个字母和字...

Anleb 2019-08-26 12:18 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
JS正则表达式入门

摘要：什么是正则表达式正则表达式其实就是，在一个字符串序列中，按照你自己想要的匹配模式，将字符串搜索或替换的过程正则表达式结构正则表达式主体修饰符可选实例如下解析是一个正则表达式，其中是一个正则表达式主体，是一个修饰符搜索不区分大小写使用正则表达什么是正则表达式？正则表达式其实就是，在一个字符串序列中，按照你自己想要的匹配模式，将字符串搜索或替换的过程正则表达式结构 /正则表达式主体/...

paraller 2019-08-23 14:09 评论0 收藏0
正则表达式基础笔记

摘要：参考资料慕课网鬼斧神工之正则表达式正则表达式后向引用详解正则表达式分钟入门教程什么是正则表达式正则表达式是字符串的搜索和匹配的工具。贪婪模式懒惰模式后向引用分组捕获的内容可以在表达式或其他程序中作进一步的处理。参考资料慕课网-鬼斧神工之正则表达式正则表达式后向引用详解正则表达式30分钟入门教程什么是正则表达式？正则表达式是字符串的搜索和匹配的工具。正则表达式工具一个测试正...

Enlightenment 2019-08-19 18:10 评论0 收藏0