題目：請實作一個函式用來匹配包括'.'和'*'的正則運算式，模式中的字符'.'表示任意一個字符，而'*'表示它前面的字符可以出現任意次（包含0次）， 在本題中，匹配是指字串的所有字符匹配整個模式，例如，字串"aaa"與模式"a.a"和"ab*ac*a"匹配，但是與"aa.a"和"ab*a"均不匹配
當模式中的第二個字符不是“*”時：
a.如果字串第一個字符和模式中的第一個字符相匹配，那么字串和模式都后移一個字符，然后匹配剩余的，
b.如果 字串第一個字符和模式中的第一個字符相不匹配，直接回傳false，
而當模式中的第二個字符是“*”時：
如果字串第一個字符跟模式第一個字符不匹配，則模式后移2個字符，繼續匹配，如果字串第一個字符跟模式第一個字符匹配，可以有3種匹配方式：
a.模式后移2字符，相當于x*被忽略；
b.字串后移1字符，模式后移2字符；
c.字串后移1字符，模式不變，即繼續匹配字符下一位，因為*可以匹配多位；
function match(s, pattern) { // write code here if (s == null || pattern == null) { return false } return checkMatch(s, pattern, 0, 0) } function checkMatch(s, pattern, i, j) { if (i === s.length && j === pattern.length) { return true } if (j === pattern.length && i !== s.length) { return false } // 第二個符號為 * if (pattern[j + 1] && pattern[j + 1] === '*') { // 第一個字符匹配 if (s[i] === pattern[j] || (pattern[j] === '.' && i !== s.length)) { return checkMatch(s, pattern, i, j + 2) || checkMatch(s, pattern, i + 1, j) || checkMatch(s, pattern, i + 1, j + 2) // 第一個字符不匹配 } else { return checkMatch(s, pattern, i, j + 2) } } //第二個字串不為* if (s[i]===pattern[j] || (pattern[j] === '.' && i !== s.length)) { return checkMatch(s, pattern, i + 1, j + 1) } return false }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27617.html
標籤：其他
上一篇：【劍指offer】演算法題03.陣列中重復的數字(C++)
下一篇：字串----表示字符的字串