Implement regular expression matching with support for
'.' and '*'.'.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → trueA:
这道题目的思路的关键就是： 优先通过消去 * 来匹配。
-----------------第五遍-----------犯了个错误，就是：刚开始不是按照第二个位置是否是 ‘*’ 来分的，而先按照第一个位置是否匹配来做，比较SB-------------
public class Solution {
public boolean isMatch(String s, String p) {
if(s.length()==0)
return p.length()==0 || (p.length()>=2 && p.charAt(1)=='*' && isMatch("",p.substring(2)));
if(p.length()==0)// s is already not zero
return false;
if( p.length() > 1 && p.charAt(1)=='*') // first case, we do not match at this position
return isMatch(s,p.substring(2)) || ( (s.charAt(0) == p.charAt(0) || p.charAt(0)=='.') && isMatch(s.substring(1),p));
else
return (s.charAt(0) == p.charAt(0) || p.charAt(0)=='.') && isMatch(s.substring(1),p.substring(1));
}
}
-----------第四遍------一遍过，不错不错---------嗯，出了2个typo-----
public class Solution {
public boolean isMatch(String s, String p) {
if(p.length() == 0)
return s.length() ==0;
if(s.length()==0 ) // now p is not empty
return p.length() != 1 && p.charAt(1) == '*' && isMatch("",p.substring(2));
// if p.length() == 1
if(p.length() ==1)
return s.length()==1 && (p.equals(s) || p.equals("."));
// now p is at least at length 2
if(p.charAt(1) != '*'){ // first char match
return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') &&isMatch(s.substring(1),p.substring(1));
}else{// we have * at p(1)
if(isMatch(s,p.substring(2)))// zero match at this position
return true;
return (s.charAt(0) == p.charAt(0) || p.charAt(0) =='.') && isMatch(s.substring(1),p);
}
}
}
--------------第一遍-----------
下面这个方法，太慢，但很好地阐述了思想。--------不对，下面的算法， 当输入是：
String s = "aaaaaaaaaaaaab";
String p = "a*a*a*a*a*a*a*a*a*a*c";
的时候，几乎陷入死进去了。 ╮(╯▽╰)╭
public class Solution {
public boolean isMatch(String s, String p) {
assert (p != null && (p.length() == 0 || p.charAt(0) != '*'));
return isMatch(s + "a", 0, p + "a", 0);
}
private boolean isMatch(String s, int startS, String p, int startP) {
for (int i = startS; i < s.length() - 1; i++) {// NOT check last char
if (startP >= p.length() - 1) {// we reach the end of pattern p
return false;
}
char chS = s.charAt(i);// will not be '.' or '*'
char chP = p.charAt(startP);
char chPnext = p.charAt(startP + 1);
if (chPnext == '*') {
if (chS == chP || chP == '.') {
if (isMatch(s, startS, p, startP + 2)) {// no match needed
return true;
}
} else {// skip this chP and '*', and retest chS
i--;
startP = startP + 2;
}
} else { // chPnext != '*'
if (chS == chP || chP == '.') {
startP++; // pattern p , also move backward
} else {
return false;
}
}
}
return true;
}
}
-------------------------------------------------------上面有bug， 会总是停在 startS= 0 ， 而 startP = 18, 20 里跳来跳去。
-------------------下面这个代码，硬是比我们的快一倍----关键是正确， ！！！！！---哎~~~~~~~~
public class Solution {
public boolean isMatch(String s, String p) {
assert(p!=null && (p.length()==0 || p.charAt(0)!='*'));
if(p.length()==0) return s.length()==0;
if(p.length()==1 || p.charAt(1)!='*'){
if(s.length()<1 || (p.charAt(0)!='.' && p.charAt(0)!=s.charAt(0)))
return false;
return isMatch(s.substring(1),p.substring(1));
}else{
int i=-1;
while(i<s.length() && (i<0 || p.charAt(0)=='.' || p.charAt(0)==s.charAt(i))){
if(isMatch(s.substring(i+1),p.substring(2)))
return true;
i++;
}
return false;
}
}
}
--------------------------上面痛苦地跟狗一样，下面是最新的思想，来自于另一个wild string matching 的苦逼思考---------------利用了split的思想-------
但是， 最终的结果，还是不能处理下面这个 输入
// idea: // pattern like a* , NOT wildmatch, move to the last match position
// This would fail at "aaa", "ab*a*c*a"
while (beginIndex< s.length() && s.charAt(beginIndex) == curChar) {
beginIndex++;
}
这里，存在的问题，就是，move to the last matching position 是不行的。 因为，下一个c*可能是不需要match的。 （move to the last matching position） 只能对nextNode.isFollowedByStar == false的情况才有用。
哎，只能用递归的方法解决了。 到底没能用线性的方法解决这个问题。
算了，不管了，归根道理， 还是得用人家的方法解决。 何苦那么费劲巴力得去String.split()呢？？
---------------------------------------------------第二遍，-----------用的是上面的substring的方式。------------要注意的问题是
1： 遇见 *的时候， 要对于是 的相等 的位置的下一个取substring。 否则~~~
2： 同上， 相应的 i 的位置，要 初始值为 -1
3： 对于 s=="” 的情况，不能简单地对应为： p = "a*"的情况， 应该归并到.*的循环里， 因为有可能是 a*a*的情况， 也是match 的。
--------------------------第三遍------------------------ 用了list来表示。 但是， 痛苦的地方，在于，不能很直观地loop, 否则的话，就会保存不了很多copy。
哎， 悲哀阿！～～～～～～悲哀的地方，见下边～～～～～～
最后，又折腾了2，3个小时，不得不返回原来的用string的方法。 最终折腾的代码如下：
思路和上面的一样。
public class Solution {
public boolean isMatch(String s, String p) {
if (p.length() == 0) {
return s.length() == 0;
}
if (s.length() == 0) { // all the list are followed by star
if (p.length() % 2 == 1) // if not all .*.* form
return false;
for (int i = 1; i < p.length(); i += 2) {
if (p.charAt(i) != '*')
return false;
}
return true;
}
if (p.length() == 1 || p.charAt(1) != '*') {
if (p.charAt(0) == '.' || p.charAt(0) == s.charAt(0)) {
return isMatch(s.substring(1), p.substring(1));
} else
return false;
} else {// current list is followed by star
if (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0)) {
return isMatch(s, p.substring(2));
} else {// find match at this position
int curMatchPos = -1;
do {
curMatchPos++;
boolean isMatchHere = isMatch(s.substring(curMatchPos),
p.substring(2));
if (isMatchHere == true)
return true;
if (curMatchPos >= s.length())
return false;
} while (p.charAt(0) == '.' || p.charAt(0) == s.charAt(curMatchPos));
return false;
}
}
}
}
主要复杂在后面跟着*的时候。
方法首先检查p 是否为空。 然后，检查 s 是否为空。
都不为空的话。
case 1： 如果p的长度==1 或者后面没有跟着*
直接对比当前的char , 看是否match
case 2: 如果当前的 p.charAt(0) , 后面跟着 * .
关键思想： 把所有的case，从递归调用，换成循环。 ，因此是在循环里， 逐个匹配p.charAt(0)。 如果当前位置匹配， 则递归调用，是否丐情况是否匹配。
这里，关键是用了一个循环，逐个匹配。
最后，所有的都没有匹配的时候， 则返回false;.
Mistakes:
1: 这个， 就是看别人的代码吧。 哎，你个SB， ，花了一晚上的时间, ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~；两年，阿金费耶夫范德萨了(#‵′)凸o(╯□╰)oo(╯□╰)oT^TT^T?_?╭∩╮（︶︿︶）╭∩╮鄙视你！╭(╯^╰)╮⊙﹏⊙b汗-_-|||?_?O(∩_∩)O~(*^◎^*)o(>﹏<)o不要啊+_+-_-#~~~^_^~~~ :）O(∩_∩)O哈哈~↖(^ω^)↗（¯﹃¯）口水我靠( ‵o′)凸~\(≧▽≦)/~啦啦啦(⊙_⊙)？( ⊙ o ⊙ )啊！(*^__^*) 嘻嘻……(⊙_⊙)(⊙v⊙)嗯
Learned:
0： 以前不知道，后来被人指出，说写文章时不能用can't ，用can not不对是个语法错误
，要用cannot。
1: 对数组取substring， 的速度，并不比用 string index慢。 所以， 以后，如果可能，还是取substring吧。~~~~~~~~~~
2; 对一个string，用 * 来分割的话， 星号前要加两个 反斜杠
String[] pArray = p.split("\\*");
同理，对于用 dot 来分割： String extensionRemoved = filename.split("\\.")[0];
---------------------------第三遍的悲哀----------------
import java.util.*;
public class Solution {
public boolean isMatch(String s, String p) {
if( s.length() == 0 && p.length() ==0){
return true;
}
ArrayList<RNode> list = new ArrayList<RNode>();
//build list
for(int i =0;i< p.length();i++){
char ch = p.charAt(i);
if(i +1 <p.length() && p.charAt(i+1) == '*'){
RNode node = new RNode(ch,true);
list.add(node);
i++;
}else{
RNode node = new RNode(ch,false);
list.add(node);
}
}
// delete repeated node, like .* .* .* or a* a* a*
for(int i =0;i<list.size()-1;i++){
if(list.get(i).isStar && list.get(i+1).isStar && list.get(i).ch == list.get(i+1).ch){
list.remove(i+1);
i--;
}
}
return isMatch(s, list);
}
public boolean isMatch(String s, ArrayList<RNode> list){
if(list.isEmpty() ){
return s.length() == 0;
}
if(s.length() ==0){ // all the list are followed by star
for(int i =0;i< list.size();i++){
if(list.get(i).isStar==false)
return false;
}
return true;
}
if( list.get(0).isStar == false){
if(list.get(0).ch =='.' || list.get(0).ch == s.charAt(0)){
list.remove(0);
return isMatch(s.substring(1),list);
}else
return false;
}else{// current list is followed by star
if( list.get(0).ch !='.' && list.get(0).ch != s.charAt(0)){ //if not match, skip this node
list.remove(0);
return isMatch(s,list);
}else{// find match at this position
// choice 1: match here, and continue with current node
char ch = list.get(0).ch;
int chCount =0;
list.remove(0);
do{
boolean curResult = isMatch(s.substring(chCount), list);
if(curResult == true)
return true;
chCount++;
if(chCount>=s.length())
return list.isEmpty();
}while(ch =='.' || ch == s.charAt(chCount));
// after trying all possible positions of node 0 in list, we test the rest
return isMatch(s.substring(chCount), list);
}
}
}
}
class RNode{
boolean isStar;
char ch;
public RNode(char ch1, boolean isFollowedByStar){
ch = ch1;
isStar = isFollowedByStar;
}
}
上边list的地方，会被递归调用，导致list被更改。(因此，还需要加一个deep copy list 的函数） 哎， 悲哀阿悲哀
还是用string吧， 每次直接substring就行了
No comments:
Post a Comment