题解 | #正则表达式匹配#
正则表达式匹配
http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
Map<String,Boolean> map = new HashMap<>();
public boolean match (String str, String pattern) {
// write code here
return isEqual(str,0,pattern,0);
return i == str.length();
int size = pattern.length()-j;
if(size % 2 == 1){
return false;
}
for( ;j < pattern.length();j += 2){
if(pattern.charAt(j+1) != '*'){
return false;
}
}
return true;
if(map.get(key)!=null){
return map.get(key);
}else{
res = isEqual(str,i+1,pattern,j+1);
}else{
res = false;
}
}
map.put(key,res);
return res;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
Map<String,Boolean> map = new HashMap<>();
public boolean match (String str, String pattern) {
// write code here
return isEqual(str,0,pattern,0);
}
//记忆搜索法
public boolean isEqual(String str,int i,String pattern,int j){
//模式移动到末尾时，通过判断字符串长度判断是否为true
if(j == pattern.length()){return i == str.length();
}
//字符串移动到末尾时，模式剩余空串或者达到空串效果例如x*y*z*
if(i == str.length()){int size = pattern.length()-j;
if(size % 2 == 1){
return false;
}
for( ;j < pattern.length();j += 2){
if(pattern.charAt(j+1) != '*'){
return false;
}
}
return true;
}
//当两下标出现过直接返回
String key = i + "," + j;if(map.get(key)!=null){
return map.get(key);
}
boolean res;
//相同时
if(str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.'){
//模式下一个字符为‘*’时
if(j<pattern.length()-1 && pattern.charAt(j+1) == '*'){
//匹配0或多个
res = isEqual(str,i+1,pattern,j)||isEqual(str,i,pattern,j+2);}else{
res = isEqual(str,i+1,pattern,j+1);
}
//不相同时
}else{
//模式下一个字符为‘*’时
if(j<pattern.length()-1&&pattern.charAt(j+1) == '*'){
//匹配0个字符
res = isEqual(str,i,pattern,j+2);}else{
res = false;
}
}
map.put(key,res);
return res;
}
}
投递腾讯等公司7个岗位
查看17道真题和解析