成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Word Pattern 單詞模式

wdzgege / 3494人閱讀

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

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.
哈希表法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

這題幾乎和Isomorphic Strings一模一樣，不同的就是之前是字母映射字母，現(xiàn)在是字母映射字符串而已。

代碼 
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);
            // 如果該字符產(chǎn)生過(guò)映射
            if(map.containsKey(p)){
                // 且映射的字符串和當(dāng)前字符串不一樣
                if(!s.equals(map.get(p))) return false;
            } else {
            // 如果該字符沒(méi)有產(chǎn)生過(guò)映射
                // 如果當(dāng)前字符串已經(jīng)被映射過(guò)了
                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.
回溯法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

因?yàn)槟繕?biāo)字符串可以任意劃分，所以我們不得不嘗試所有可能性。這里通過(guò)深度優(yōu)先搜索的回溯法，對(duì)于pattern中每個(gè)字母，在str中嘗試所有的劃分方式，如果劃分出來(lái)的子串可以用這個(gè)字母映射，或者可以建立一個(gè)新的字母和字符串的映射關(guān)系，我們就繼續(xù)遞歸判斷下一個(gè)pattern中的字母。

代碼 
public class Solution {
    
    Map map;
    Set set;
    boolean res;
    
    public boolean wordPatternMatch(String pattern, String str) {
        // 和I中一樣，Map用來(lái)記錄字符和字符串的映射關(guān)系
        map = new HashMap();
        // Set用來(lái)記錄哪些字符串被映射了，防止多對(duì)一映射
        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也正好匹配完了，說(shuō)明有解
        if(i == pattern.length() && j == str.length()){
            res = true;
            return;
        }
        // 如果某個(gè)匹配超界了，則結(jié)束遞歸
        if(i >= pattern.length() || j >= str.length()){
            return;
        }
        char c = pattern.charAt(i);
        // 嘗試從當(dāng)前位置到結(jié)尾的所有劃分方式
        for(int cut = j + 1; cut <= str.length(); cut++){
            // 拆出一個(gè)子串
            String substr = str.substring(j, cut);
            // 如果這個(gè)子串沒(méi)有被映射過(guò)，而且當(dāng)前pattern的字符也沒(méi)有產(chǎn)生過(guò)映射
            // 則新建一對(duì)映射，并且繼續(xù)遞歸求解
            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);
            // 如果已經(jīng)有映射了，但是是匹配的，也繼續(xù)求解
            } else if(map.containsKey(c) && map.get(c).equals(substr)){
                helper(pattern, str, i + 1, cut);
            }
            // 否則跳過(guò)該子串，嘗試下一種拆分
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64664.html

相關(guān)文章

  • 890-查找和替換模式

    摘要：前言的的題目查找和替換模式，原題目描述如下你有一個(gè)單詞列表和一個(gè)模式，你想知道中的哪些單詞與模式匹配。如果存在字母的排列，使得將模式中的每個(gè)字母替換為之后，我們就得到了所需的單詞，那么單詞與模式是匹配的。 前言 LeetCode的Weekly Contest 98的題目查找和替換模式，原題目描述如下： 你有一個(gè)單詞列表 words 和一個(gè)模式 pattern，你想知道 words 中...

    haobowd 評(píng)論0 收藏0

  • LeetCode 290 單詞模式 JS實(shí)現(xiàn)

    摘要：給定一種模式和一個(gè)字符串，判斷是否遵循相同的模式。這里的遵循指完全匹配，例如，里的每個(gè)字母和字符串中的每個(gè)非空單詞之間存在著雙向連接的對(duì)應(yīng)模式。示例輸入輸出示例輸入輸出說(shuō)明你可以假設(shè)只包含小寫字母，包含了由單個(gè)空格分隔的小寫字母。 給定一種 pattern(模式) 和一個(gè)字符串 str ，判斷 str 是否遵循相同的模式。 這里的遵循指完全匹配，例如， pattern 里的每個(gè)字母和字...

    Anleb 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • JS正則表達(dá)式入門

    摘要：什么是正則表達(dá)式正則表達(dá)式其實(shí)就是，在一個(gè)字符串序列中，按照你自己想要的匹配模式，將字符串搜索或替換的過(guò)程正則表達(dá)式結(jié)構(gòu)正則表達(dá)式主體修飾符可選實(shí)例如下解析是一個(gè)正則表達(dá)式，其中是一個(gè)正則表達(dá)式主體，是一個(gè)修飾符搜索不區(qū)分大小寫使用正則表達(dá) 什么是正則表達(dá)式？ 正則表達(dá)式其實(shí)就是，在一個(gè)字符串序列中，按照你自己想要的匹配模式，將字符串搜索或替換的過(guò)程 正則表達(dá)式結(jié)構(gòu) /正則表達(dá)式主體/...

    paraller 評(píng)論0 收藏0

  • 正則表達(dá)式基礎(chǔ)筆記

    摘要：參考資料慕課網(wǎng)鬼斧神工之正則表達(dá)式正則表達(dá)式后向引用詳解正則表達(dá)式分鐘入門教程什么是正則表達(dá)式正則表達(dá)式是字符串的搜索和匹配的工具。貪婪模式懶惰模式后向引用分組捕獲的內(nèi)容可以在表達(dá)式或其他程序中作進(jìn)一步的處理。 參考資料 慕課網(wǎng)-鬼斧神工之正則表達(dá)式正則表達(dá)式后向引用詳解正則表達(dá)式30分鐘入門教程 什么是正則表達(dá)式？ 正則表達(dá)式是字符串的搜索和匹配的工具。 正則表達(dá)式工具 一個(gè)測(cè)試正...

    Enlightenment 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<