今天的題目上難度了，是困難難度的動(dòng)態(tài)規(guī)劃
標(biāo)簽：動(dòng)態(tài)規(guī)劃、位運(yùn)算
劍指 Offer 19. 正則表達(dá)式匹配
這個(gè)題給題意轉(zhuǎn)換一下就是字符串匹配，而字符串匹配我們能想到滑動(dòng)窗口、KMP算法；KMP算法其實(shí)也算是動(dòng)態(tài)規(guī)劃；這個(gè)題其實(shí)也是需要用動(dòng)態(tài)規(guī)劃的思想去解決的
說(shuō)明boolean[][]?dp?=?new?boolean[s.len+1][p.len+1] dp[i][j]=true表示s[i-1]與p[j-1]匹配
題干給出p字符串比s字符串多'.' '*'這兩種字符。'.'很好處理，因?yàn)樗槐硎疽粋€(gè)能任意匹配的字符；'*'的情況就復(fù)雜的多了，它需要與前一個(gè)字符搭配使用能表示0個(gè)或多個(gè)字符，因此我們根據(jù)p[j]是否為*來(lái)
分情況討論：
當(dāng)p[j] == '*'時(shí)：
1. s從0到i與p從0到j(luò)-2匹配，即p[j-1]p[j]代表0：dp[i][j-2]==true && p[j]=='*'
2. s從0到i-1與p從0到j(luò)匹配且s[i] == p[j-1]：dp[i-1][j]==true && (s[i-1] == p[j-2] || p[j-2] == '.')
當(dāng)p[j] != '*'時(shí)
1. s從0到i-2與p從0到j(luò)-2匹配且 s[i-1]==p[i-1]匹配：dp[i-1][j-1] == true && (s[i-1]==p[j-1] || p[j-1]=='.')
初始化
動(dòng)態(tài)規(guī)劃dp表的初始化dp[0][0]=true，對(duì)s[0]時(shí)需要對(duì)p[2k]=='*'? (k=1,2,3...)做初始化
318. 最大單詞長(zhǎng)度乘積
直觀解法就是暴力搜索，使用hashSet存儲(chǔ)每個(gè)word的字符，再逐字符查詢(xún)isContain()。word與word之間的比較一定是n^2的時(shí)間復(fù)雜度，所以?xún)?yōu)化的關(guān)鍵點(diǎn)就在將word轉(zhuǎn)換成26位長(zhǎng)的表示改位的字符是否存在的數(shù)字（題干給出只存在小寫(xiě)字母）。思路如果沒(méi)見(jiàn)過(guò)的話，比較難想到
判斷 兩個(gè)對(duì)象是否相等 -> hash -> 很多情況下hash可以用數(shù)組代替 -> 位運(yùn)算，與或非
