第GoJava算法之單詞規(guī)律示例詳解目錄單詞規(guī)律方法一：哈希表（Java）方法一：哈希表（GO）

單詞規(guī)律

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

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

輸入:pattern=abba,s=dogcatcatdog

輸出:true

示例2:

輸入:pattern=abba,s=dogcatcatfish

輸出:false

示例3:

輸入:pattern=aaaa,s=dogcatcatdog

輸出: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為當前遍歷的索引

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

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

classSolution{

publicbooleanwordPattern(Stringpattern,Stringstr){

MapString,Characterstr2ch=newHashMapString,Character

MapCharacter,Stringch2str=newHashMapCharacter,String

intm=str.length();

inti=0;

for(intp=0;ppattern.length();++p){

charch=pattern.charAt(p);

if(i=m){

returnfalse;

intj=i;

while(jmstr.charAt(j)!=''){

j++;

Stringtmp=str.substring(i,j);

if(str2ch.containsKey(tmp)str2ch.get(tmp)!=ch){

returnfalse;

if(ch2str.containsKey(ch)!tmp.equals(ch2str.get(ch))){

returnfalse;

str2ch.put(tmp,ch);

ch2str.put(ch,tmp);

i=j+1;

returni

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

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

方法一：哈希表（GO）

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

具體方法：

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

str=dogcatcatdog，轉(zhuǎn)成0110

funcwordPattern(patternstring,strstring)bool{

p:=strings.Split(pattern,"")

s:=strings.Split(str,"")

iflen(p)!=len(s){

returnfalse

pNum,sNum:=0,0

pString,sString:="",""

pMap:=map[string]int{}

sMap:=map[string]int{}

for_,v:=rangep{

if_,ok:=pMap[v];ok{

pString+=strconv.Itoa(pMap[v])

}else{

pString+=strconv.Itoa(pNum)

pMap[v]=pNum

pNum++

for_,v:=ranges{

if_,ok:=sMap[v];ok{

sString+=strconv.Itoa(sMap[v])

}else{

sString+=strconv.Itoa(sNum)

sMap[v]=sNum

sNum++

ifpString==sString{