java 实现含通配符的字符串匹配

算法目标，对于 字符串 abcd1dd2deeedd9 能偶匹配到字符串 abc*dd?；*代表任意个数的字符串，？代表一个字符.

分两步走，

第一步实现含？而不含*的 字符串匹配，如对dd？的匹配 

第二步，实现含有* 的字符串的匹配，如abc* dd?，主要思路是用* split 字符串，分为两个有效的串，abc, dd?

然后使用步骤一种的方法来查看匹配到的index.

 

 

 /**

   * 找出含？的字符串

   * @return

   */

  public int checkSubPattern(String src,int begin,String pat){

  boolean isFound=true;

  if(src.length()-begin < pat.length()){return -1;}

  for(int i=begin;i<src.length()-pat.length()+1;i++){

  for(int j=0;j<pat.length();j++){

  if(pat.charAt(j)!='?' && src.charAt(i+j)!=pat.charAt(j)){

  isFound =false;

  break;

  }

  isFound = true;

  }

  if(isFound){return i;}

  }

  return -1;

  }

 

 

 

  public boolean checkStar(String src,String pat){

  String[] sub_p = pat.split("\\*");

 

  int begin =0;

  for(int i=0;i< sub_p.length;i++){

 

   begin = checkSubPattern(src,begin,sub_p[i]);

   System.out.println(begin);

   if(begin==-1){return false;}

   if(i==0 && pat.charAt(i)!='*' &&begin!=0){return false;}

   if((i==sub_p.length-1)  && pat.charAt(i)!='*' &&begin!=(src.length()-                                      sub_p[i].length())){return false;}

  }

  return true;

  }

 

评论

3 楼 瓶鱼跃 2012-11-01  

测试了楼主的方法，用楼主的字符串，怎么返回的是false？？

2 楼 sunlujing 2012-10-29  

面试题，不让用正则表达式，他其实就是想让你分析下正则表达式的内部实现

1 楼 muyishuihan 2012-10-29  

为什么不用正则表达式做呢？
public static boolean isMatching(String src,String des){

String des1 = des.replace("*", "\\w*");
des1 = des1.replace("?", "\\w{1}");
Pattern p = Pattern.compile(des1);
Matcher m = p.matcher(src);
return m.matches();
}