刷题过程中遇到的正则表达式使用
最前面
- 有的题目本身时解决通配问题；
- 有的题目可以巧妙的用通配符解决；
华为机试：字符串通配符
三种解法
- 递归
- 通配符
- 动态规划
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String in;
while((in = br.readLine())!=null){
String temp = br.readLine();
//System.out.println(isMatch(temp,in));
System.out.println(getOc(in,temp));
//System.out.println(getOc(in,temp,0,0));
}
}
public static boolean getOc(String s1,String s2,int p1,int p2){
//递归求解
//base case
if (p1 == s1.length() && p2 == s2.length()){
return true;
}else if (p1 == s1.length() || p2 == s2.length()){
return false;
}
//遇到'*'两种情况，要不就各跳过一个比较后面，要不就s2继续往后跳先不比较
if (s1.charAt(p1) == '*'){
return getOc(s1, s2, p1, p2+1) || getOc(s1, s2, p1+1, p2+1);
//遇到'?'跟两个一样操作一样，直接指针都往后移一个继续比较
}else if (s1.charAt(p1) == '?' || s1.charAt(p1) == s2.charAt(p2)){
return getOc(s1, s2, p1+1, p2+1);
}else {
return false;
}
}//method end
public static boolean getOc(String in,String temp){
//字符串通配符
in = in.replaceAll("\\?", "[0-9A-Za-z]{1}");
in = in.replaceAll("\\*", "[0-9A-Za-z]{0,}");//
//in = in.replaceAll("\\.", "\\\\.");
return temp.matches(in);
}
public static boolean isMatch(String s, String p) {
//动态规划
if(s.length() == 0 && p.length() == 0)return true;
if(s.length()!= 0 && p.length() == 0) return false;
boolean [][] dp = new boolean [s.length()+1][p.length()+1];
dp[0][0] = true;
for(int j = 2; j <= p.length(); j++){
if(p.charAt(j-1) == '*' && dp[0][j-2]){
dp[0][j] = true;
}
}
for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <= p.length(); j++){
char a = s.charAt(i-1), b = p.charAt(j-1);
if(a == b || b == '?'){
dp[i][j] = dp[i-1][j-1];
}
else if(b == '*'){
if(j>=2){
dp[i][j] = dp[i-1][j] || dp[i][j-2];
}
}
else dp[i][j] = false;
}
}
return dp[s.length()][p.length()];
}
}
剑指offer:53.表示数值的字符串
思路1
- +-号后面必定为数字或后面为.（-.123 = -0.123）
- +-号只出现在第一位或在eE的后一位
- .后面必定为数字或为最后一位（233. = 233.0）
- eE后面必定为数字或+-号
代码
public class Solution {
public boolean isNumeric(char[] str) {
boolean point = false, exp = false; // 标志小数点和指数
for (int i = 0; i < str.length; i++) {
if (str[i] == '+' || str[i] == '-') {
// +-号后面必定为数字 或 后面为.（-.123 = -0.123）
if (i + 1 == str.length || !(str[i + 1] >= '0' && str[i + 1] <= '9' || str[i + 1] == '.')) {
return false;
}
// +-号只出现在第一位或eE的后一位
if (!(i == 0 || str[i-1] == 'e' || str[i-1] == 'E')) {
return false;
}
} else if (str[i] == '.') {
if (point || exp || !(i + 1 < str.length && str[i + 1] >= '0' && str[i + 1] <= '9')) { // .后面必定为数字 或为最后一位（233. = 233.0）
return false;
}
point = true;
} else if (str[i] == 'e' || str[i] == 'E') {
if (exp || i + 1 == str.length || !(str[i + 1] >= '0' && str[i + 1] <= '9' || str[i + 1] == '+' || str[i + 1] == '-')) { // eE后面必定为数字或+-号
return false;
}
exp = true;
} else if (str[i] >= '0' && str[i] <= '9') {
} else {
return false;
}
}
return true;
}
}
思路2
正则表达式大法
[] ： 字符集合
() ： 分组
? ： 重复 0 ~ 1 次
+ ： 重复 1 ~ n 次
* ： 重复 0 ~ n 次
. ： 任意字符
\\. ： 转义后的 .
\\d ： 数字
{n} ：必须匹配n次
{n,}：必须匹配n次或以上
{n,m}：匹配次数在n到m之间，包括边界
代码
public class Solution {
public boolean isNumeric(char[] str) {
if (str == null || str.length == 0)
return false;
return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
}
}
剑指offer:52.正则表达式匹配
思路1 递归匹配
当模式中的第二个字符不是“*”时： 1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。 2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第二个字符是“”时： 可以有3种匹配方式： 1、模式后移2字符，相当于x被忽略；匹配0位 2、字符串后移1字符，模式后移2字符，x相当于只匹配一个字符； 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为可以匹配多位；（包括匹配一位）
- 如果pattern[j] == ‘.’
- 如果str[i] == pattern[j]
以上两种情况都是i后移一位，然后j后移一位。
而当模式中的第二个字符是“*”时：
- 如果
pattern[i] == '.' || str[i] == pattern[j],那么证明第一位相匹配，需要匹配0或多位matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j)； - 反之，j后移两位。
代码
public class Solution {
public boolean matchStr(char[] str, int i, char[] pattern, int j) {
if (i == str.length && j == pattern.length) { // 字符串和模式串都为空
return true;
} else if (j == pattern.length) { // 模式串为空
return false;
}
boolean next = (j + 1 < pattern.length && pattern[j + 1] == '*');// 模式串下一个字符是'*'
//当模式中的第二个字符是“*”时：
if (next) {
if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
//匹配零位 & 匹配多位 （即使这一位相同或者是.，也有可能只匹配零位，匹配一位的情况包含在递归里了）
return matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j);
} else {
//匹配零位（当这一位不相同而且还不是.的时候，只能忽略了）
return matchStr(str, i, pattern, j + 2);
}
}
//当模式中的第二个字符不是“*”时：
else {
//匹配一位
if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
return matchStr(str, i + 1, pattern, j + 1);
} else {
//匹配这一位失败
return false;
}
}
}
public boolean match(char[] str, char[] pattern) {
return matchStr(str, 0, pattern, 0);
}
}
思路2 动态规划
动态规划转移方程：
boolean dp[i][j]表示str的前i个和pattern的前j个能否匹配
第一个字符为str[0]
从pattern角度看过去
第j个字符，当前字符pattern[j-1]不是“*”：
如果 pattern[j-1] == '.' || str[i-1] == pattern[j-1])，dp[i][j] = dp[i-1][j-1]
否则，dp[i][j] =false;
第j个字符，当前字符pattern[j-1]是“*”：
比较pattern中前一字符pattern[j-2]与str[i-1]是否匹配
如果 pattern[j-2] == '.' || str[i-1] == pattern[j-2])，那么分两种情况
-
如果重复0次，dp[i][j] = dp[i][j-2]
-
如果重复1次或者多次，dp[i][j] = dp[i-1][j]
否则，
- 只有重复0次，dp[i][j] = dp[i][j-2]
动态规划初始条件：
str为空且pattern为空，为真: dp[0][0] = true
str不为空且pattern为空,为假: dp[1..sn][0] = false
pattern[j-1]==’*‘时,dp[0,j]=dp[0,j-2]; 否则dp[0,j]=false;
public class Solution {
public boolean judge(char p,char s){
if(p=='.')return true;
else return p==s;
}
public boolean match(char[] str, char[] pattern)
{
int pn=pattern.length;
int sn=str.length;
boolean[][] dp=new boolean[sn+1][pn+1];
//初始化
dp[0][0]=true;
for(int j=1;j<=pn;j++){
if(pattern[j-1]=='*')dp[0][j]=dp[0][j-2];
}
for(int i=1;i<=sn;i++){
for(int j=1;j<=pn;j++){
boolean now = (pattern[j-1] == '*');// 模式串当前字符是'*'
if(!now){
if(judge(pattern[j-1],str[i-1]))
dp[i][j]=dp[i-1][j-1];
}
else{
if(judge(pattern[j-2],str[i-1]))
dp[i][j]=dp[i][j-2]|dp[i-1][j];
else dp[i][j]=dp[i][j-2];
}
}
}
return dp[sn][pn];
}
}
思路3 和原正则表达式一致，使用库函数匹配
public class Solution {
public boolean match(char[] str, char[] pattern)
{
return String.valueOf(str).matches(String.valueOf(pattern));
}
}
import java.util.regex.*;
public class Solution {
public boolean match(char[] str, char[] pattern)
{
String pat = String.valueOf(pattern);
//把.替换为正则表达式的\w 用以匹配一个任意字符
pat = pat.replaceAll("\\.", "\\\\w");
Pattern pattern1 = Pattern.compile(pat);
Matcher matcher = pattern1.matcher(String.valueOf(str));
return matcher.matches();
}
}
车轮滚滚 时间
import java.util.regex.*;
[] ： 字符集合
() ： 分组
? ： 重复 0 ~ 1 次
+ ： 重复 1 ~ n 次
* ： 重复 0 ~ n 次
. ： 任意字符
\\. ： 转义后的 .
\\d ： 数字
{n} ：必须匹配n次
{n,}：必须匹配n次或以上
{n,m}：匹配次数在n到m之间，包括边界
[+-]?\d*(\.\d+)?([eE][+-]?\d+)?
public String replaceAll(String regex, String replacement)
实现如下2个通配符：
*：匹配0个或以上的字符（字符由英文字母和数字0-9组成，不区分大小写。下同）
？：匹配1个字符
/*
public String replaceAll(String regex, String replacement)
参数
regex -- 匹配此字符串的正则表达式。
newChar -- 用来替换每个匹配项的字符串。
返回值
成功则返回替换的字符串，失败则返回原始字符串。
*/
public static boolean getOc(String in,String temp){
//字符串通配符
in = in.replaceAll("\\?", "[0-9A-Za-z]{1}");
in = in.replaceAll("\\*", "[0-9A-Za-z]{0,}");
//in = in.replaceAll("\\.", "\\\\.");
return temp.matches(in);
}
//@TEST
String in = new String("te?t*.*");
System.out.println(in.replaceAll("\\?", "[0-9A-Za-z]{1}"));
//te[0-9A-Za-z]{1}t*.*
System.out.println(in.replaceAll("\\*", "[0-9A-Za-z]{0,}"));
//te?t[0-9A-Za-z]{0,}.[0-9A-Za-z]{0,}
//注意事项 怕错 下面这种组合 表示
System.out.println("".matches("[eE][+-]?"));//false
System.out.println("e".matches("[eE][+-]?"));//true
System.out.println("e+".matches("[eE][+-]?"));//true
System.out.println("+".matches("[eE][+-]?"));//false
System.out.println(".333".matches("\\.\\d+"));//true
System.out.println("3".matches("\\.\\d+"));//false
System.out.println("..3".matches("\\.\\d+"));//false
System.out.println("7".matches("[0-9A-Za-z]{1}"));//true
System.out.println("a".matches("[0-9A-Za-z]{1}"));//true
System.out.println("Q".matches("[0-9A-Za-z]{1}"));//true
再来审视这个匹配
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
规则抽象
- +-号后面必定为数字或后面为.（-.123 = -0.123）
- +-号只出现在第一位或在eE的后一位
- .后面必定为数字或为最后一位（233. = 233.0）
- eE后面必定为数字或+-号
public class Solution {
public boolean isNumeric(char[] str) {
if (str == null || str.length == 0)
return false;
return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
}
}
