恒生电子笔试4.18

• dp，设f[i][j]为匹配s到i，t串到j位置是否合法0/1，当tj='.'，tj必须与si匹配，f[i][j]由f[i-1][j-1]转移，

当tj='*', f[i][j]由f[k][j-2]转移，1<=k<=i,必须check中间的字符都为t[j-1]，可以转移, 其余情况，只需要判断si是否=tj，然后

从f[i-1][j-1]转移即可

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String s=in.next();
        String t=in.next();
             
        if(s.length()==0||t.length()==0){
            if(s.length()==0&&t.length()==0){
                 System.out.println(1);
            }else{
                 System.out.println(0);
            }
            return;
        }
        s=' '+s;
        t=' '+t;
        int[][] f=new int[30][30];
        f[0][0]=1;
        if(t.charAt(1)=='*') f[0][1]=1;
        for(int i=1;i<s.length();i++){
            for(int j=1;j<t.length();j++){
                if(t.charAt(j)=='.'){
                    f[i][j]|=f[i-1][j-1];
                }else if(t.charAt(j)=='*'){
                    f[i][j]|=f[i][j-2];
                    for(int k=i;k>=1;k--){
                        if(check(k,i,s,t.charAt(j-1))){
                            f[i][j]|=f[k-1][j-2];
                        }
                    }
                }else{
                    if(s.charAt(i)!=t.charAt(j)) f[i][j]=0;
                    else{
                        f[i][j]|=f[i-1][j-1];
                    }
                }
              //  System.out.println(i+" "+j+" "+f[i][j]);
            }
                // System.out.println();
        }
        System.out.println(f[s.length()-1][t.length()-1]);
    }

    public static boolean check(int s,int t,String res,char x){
        for(int i=s;i<=t;i++){
            if(res.charAt(i)!=x) return false;
        }
        return true;
    }
}

• 维护每个数的max时间和min时间。判断[t-2，t]的max-min(t)是否大于等于5即可，代码没存就不写了，比较简单