Go Java算法之單詞規(guī)律示例詳解

更新時間：2022年08月20日 16:23:45 作者：黃丫丫

這篇文章主要為大家介紹了Go Java算法之單詞規(guī)律示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

單詞規(guī)律

給定一種規(guī)律 pattern 和一個字符串 s ，判斷 s 是否遵循相同的規(guī)律。

這里的遵循指完全匹配，例如， pattern 里的每個字母和字符串 s 中的每個非空單詞之間存在著雙向連接的對應(yīng)規(guī)律。

示例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 不包含任何前導(dǎo)或尾隨對空格

s 中每個單詞都被單個空格分隔

方法一：哈希表（Java）

在本題中，我們需要判斷字符與字符串之間是否恰好一一對應(yīng)。即任意一個字符都對應(yīng)著唯一的字符串，任意一個字符串也只被唯一的一個字符對應(yīng)。在集合論中，這種關(guān)系被稱為「雙射」。

想要解決本題，我們可以利用哈希表記錄每一個字符對應(yīng)的字符串，以及每一個字符串對應(yīng)的字符。然后我們枚舉每一對字符與字符串的配對過程，不斷更新哈希表，如果發(fā)生了沖突，則說明給定的輸入不滿足雙射關(guān)系。

題目本質(zhì)上是讓我們判斷str中的字符是否與pattern中的字符一一對應(yīng)

也就是說，pattern中相同的字符在str中也應(yīng)該相同，不同的字符在str中也應(yīng)該不同

我們可以通過一個字典記錄pattern中每個字符第一次出現(xiàn)的位置，即dict[x]=pattern.index(x)。然后我們遍歷對pattern中的每個字母，

記i為當(dāng)前遍歷的索引

則dict[pattern[i]]為pattern中字符pattern[i]的上個索引

判斷str中兩個索引所對應(yīng)的字母是否相同，若不同則返回False

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch2str = 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) != ' ') {
                j++;
            }
            String tmp = str.substring(i, j);
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
                return false;
            }
            if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) {
                return false;
            }
            str2ch.put(tmp, ch);
            ch2str.put(ch, tmp);
            i = j + 1;
        }
        return i >= m;
    }
}

時間復(fù)雜度：O（n+m）

空間復(fù)雜度：O（n+m）

方法一：哈希表（GO）

具體的方法思路內(nèi)容已經(jīng)在上文中表述，詳情請看上文內(nèi)容

具體方法：

pattern = "abba", 轉(zhuǎn)成0110

str = "dog cat cat dog"，轉(zhuǎn)成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
}

時間復(fù)雜度：O（n+m）

空間復(fù)雜度：O（n+m）

以上就是Go Java算法之單詞規(guī)律示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go Java算法單詞規(guī)律的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: