leetcode4/WildcardMatching.java at master · 1code/leetcode4 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//dp: could not pass the large test. TLE
public class Solution {
    public boolean isMatch(String s, String p) {
        // Start typing your Java solution below
        // DO NOT write main() function
    	String pr="";
		boolean cstar = false;
		int count = 0;
		for(int i=0; i<p.length(); i++){
			if(p.charAt(i)!='*'){
				pr+= p.charAt(i);
				cstar=false;
			}
			else{
				if(!cstar){
					cstar=true;
					pr+=p.charAt(i);
				}
			}

		}

    	int lens = s.length();
		int lenp = pr.length();

		if(lenp==0)
			return lens==0;
		else if (lens== 0)
            return pr.equals("*");

		int[][] path = new int[lenp+1][lens+1];
		path[0][0] =1;

		for(int i=1; i<lenp+1; i++){
			if(pr.charAt(i-1)=='*')
				path[i][0] =1;
			else
				break;
		}

		for(int i=1; i<lenp+1; i++)
			for(int j=1; j<lens+1; j++){
				if(pr.charAt(i-1)=='*'){
					if(path[i-1][j]==1 || path[i][j-1]==1 || path[i-1][j-1]==1)
						path[i][j]=1;
				}
				else if(pr.charAt(i-1)=='?'){
					if(path[i-1][j-1]==1)
						path[i][j]=1;
				}
				else{
					if(pr.charAt(i-1)==s.charAt(j-1) && path[i-1][j-1]==1)
						path[i][j]=1;
				}
			}

		if(path[lenp][lens]==0)
			return false;
		else
			return true;
    }
}


//recursion: Could not pass the large test. TLE
public class Solution {
    public boolean isMatch(String s, String p) {
        // Start typing your Java solution below
        // DO NOT write main() function

        int i = 0, j = 0;

        //the following is a recursive one, it timed out on large input
        if (p.length() == 0) {
            return s.length() == 0;
        }
        if (s.length() == 0) {
            return p.equals("") || allStar(p);
        }

        if (s.charAt(0) == p.charAt(0) || p.charAt(0) == '?') {
            return isMatch(s.substring(1), p.substring(1));
        }

        if (p.charAt(0) == '*') {
            return isMatch(s.substring(1), p) || isMatch(s, p.substring(1));
        }

        return false;
    }

    public boolean allStar (String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '*') {
                return false;
            }
        }

        return true;
    }
}