[LeetCode] 10. Regular Expression Matching java

2019-11-06 06:19:15

字體：大中小

來源：轉載

供稿：網友

/**10. Regular ExPRession Matching * @param s * @param p * @returnboolean 正則匹配，字符串s是否滿足p，支持'.' and '*'. */ public boolean isMatch(String s, String p) { 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)); }

//遞歸

改進：

public boolean isMatch1(String s, String p) { if (p.length() == 0) { return s.length() == 0; } if (p.length() == 1) { return s.length() == 1 && (p.charAt(0) == '.' || p.charAt(0) == s.charAt(0)) ; } // p.length() i bigger than 1 here if (p.charAt(1) == '*') { if (isMatch(s, p.substring(2))) { return true; } return s.length() > 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)) && isMatch(s.substring(1), p); } else { return s.length() > 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)) && isMatch(s.substring(1), p.substring(1)); } }

//取消while循環，全部使用遞歸

上一篇：[LeetCode] 14. Longest Common Prefix java

下一篇：[LeetCode] 5. Longest Palindromic Substring java