lintcode-正则表达式匹配

Java版

public boolean isMatch(String s, String p) {
        // write your code here
        if (p.length() == 0)
            return s.length() == 0;

        if (p.length() == 1)
            return (s.length() == 1) && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');

        if (p.charAt(1) != '*')
        {
            if (s.length() == 0)
                return false;
            else
                return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')
                       && isMatch(s.substring(1), p.substring(1));
        }
        else
        {
            while (s.length() > 0 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'))
            {
                if (isMatch(s, p.substring(2)))
                    return true;
                s = s.substring(1);
            }
            return isMatch(s, p.substring(2));
        }
    }

http://blog.csdn.net/derrantcm/article/details/46951847
import java.util.Arrays;

public class Solution {
    /**
     * 010-Regular Expresssion Matching（正则表达式匹配）
     * 
     * @param s 匹配串
     * @param p 模式串
     * @return 匹配结果，true匹配，false不匹配
     */
    public boolean isMatch(String s, String p) {
        // 标记数数组
        boolean[] match = new boolean[s.length() + 1];
        // 初始化
        Arrays.fill(match, false);
        // 假定最后的结果是匹配的
        match[s.length()] = true;
        
        //要判断p的长度
        if (p.length() == 1)
            return (s.length() == 1) && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');

        // 对模式串从后向前进行处理
        for (int i = p.length() - 1; i >= 0; i--) {

            // 如果当前是*
            if (p.charAt(i) == '*') {

                // 匹配串从最后一个开始处理
                for (int j = s.length() - 1; j >= 0; j--)  {
                    match[j] = match[j] || match[j + 1] && (p.charAt(i - 1) == '.' || s.charAt(j) == p.charAt(i - 1));
                }
                i--;
            }
            // 如果不是*
            else {
                for (int j = 0; j < s.length(); j++) {
                    match[j] = match[j + 1] && (p.charAt(i) == '.' || p.charAt(i) == s.charAt(j));
                }

                match[s.length()] = false;
            }
        }
        return match[0];
    }
}

C++版,有bug

bool isMatch(const char *s, const char *p) {
        // write your code here
        
        if(strlen(s) == 0 && strlen(p) == 0) {
            return true;
        }
        
        if(strlen(p) == 1)
            return strlen(s) == 1 && (s[0] == p[0] || p[0] == '.');
        
        if(p[1] == '*') {
            while(strlen(s) > 0 && s[0] == p[0] || p[0] == '.') {
                if(isMatch(s, p+2)) {
                    return true;
                }
                
                s++;
            }
            
            return isMatch(s, p+2);
        }
        else 
        {
            if(strlen(s) == 0) {
                return false;
            }
            
            if(s[0] == p[0] || p[0] == '.') {
                return isMatch(s+1, p+1);
            }
        }
        
        
        
        return false;
    }