[Leetcode] Word Pattern 單詞模式

wdzgege 發布于2019-08-14 12:43 / 3418人閱讀

摘要：哈希表法復雜度時間空間思路這題幾乎和一模一樣，不同的就是之前是字母映射字母，現在是字母映射字符串而已。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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