面試10大算法題匯總-字符串和數組4
來源：程序員人生 發布時間：2015-03-27 07:50:48 閱讀次數：2456次
6.匹配正則表達式
編寫函數boolisMatch(String s, String p)，完成正則表達式中“.”和“*”的功能。例：
isMatch("aa","a")return false
isMatch("aa","aa")return true
isMatch("aaa","aa")return false
isMatch("aa", "a*")return true
isMatch("aa", ".*")return true
isMatch("ab", ".*")return true
isMatch("aab", "c*a*b")return true
注：p的第1個字符不為*，且p中不會出現兩個*連接在1起的情況
可將問題分為以下幾種情況斟酌：
1. p的長度為0：此時s的長度必須為0才匹配
2. p的長度為1：若s的長度小于1，則必定不匹配。否則若p.charAt(0)不為“.”或與s不相等則不匹配
3. p的長度>1：
此處罰兩種可能斟酌：I.p.charAt(1) != '*'
II.p.charAt(1) == ‘*
當p.charAt(1) != '*'時，若s的長度小于1，則必定不匹配。比較s與p的第1個字符是不是匹配：若s與p的第1個字符不同且p的第1個字符不為”.”，則不匹配。否則迭代調用函數，返回isMatch(s.substring(1),p.substring(1))
當p.charAt(1) == '*'時，
。。。
PS:代碼有問題：
http://www.programcreek.com/2012/12/leetcode-regular-expression-matching-in-java/
比以下面代碼的測試就失敗了，暫時沒想到解決方法：
public class test {
public static boolean isMatch(String s, String p) {
// base case
if (p.length() == 0) {
return s.length() == 0;
}
// special case
if (p.length() == 1) {
// if the length of s is 0, return false
if (s.length() < 1) {
return false;
}
//if the first does not match, return false
else if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
return false;
}
// otherwise, compare the rest of the string of s and p.
else {
return isMatch(s.substring(1), p.substring(1));
}
}
// case 1: when the second char of p is not '*'
if (p.charAt(1) != '*') {
if (s.length() < 1) {
return false;
}
if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
return false;
} else {
return isMatch(s.substring(1), p.substring(1));
}
}
// case 2: when the second char of p is '*', complex case.
else {
//case 2.1: a char & '*' can stand for 0 element
if (isMatch(s, p.substring(2))) {
return true;
}
//case 2.2: a char & '*' can stand for 1 or more preceding element,
//so try every sub string
int i = 0;
while (i<s.length() && (s.charAt(i)==p.charAt(0) || p.charAt(0)=='.')){
if (isMatch(s.substring(i + 1), p.substring(2))) {
return true;
}
i++;
}
return false;
}
}
public static void main(String[] args) {
System.out.println(isMatch("12", "1*12"));
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
