Problem
Given a regular expression with characters a-z, ' * ', ' . 'the task was to find if that string could match another string with characters from: a-z
where ' * ' can delete the character before it, and ' . ' could match whatever character. ' * ' always appear after a a-z character.
Example:
isMatch("a*", "") = true;
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;
Solution
package myPackage;
public class Regex {
boolean match(String r, String in)
{
int j= 0;
for(int i= 0; i< r.length(); i++)
{
if(j >= in.length()) return false;
if(r.charAt(i) != '.' && r.charAt(i) != '+'
&& r.charAt(i) != '*'
&& r.charAt(i) != '?')
{
int k = i+1;
if((k< r.length() && r.charAt(k) != '.'
&& r.charAt(k) != '+'
&& r.charAt(k) != '*'
&& r.charAt(k) != '?')
|| k == r.length())
{
if(j< in.length()
&& in.charAt(j)==r.charAt(i))
j++;
else return false;
i--;
}
else if(r.charAt(k) == '*')
while(j< in.length()
&& r.charAt(i) == in.charAt(j))
{j++;}
else if(r.charAt(k) == '?')
if(r.charAt(i) == in.charAt(j))
{j++;}
else if(r.charAt(k) == '+')
if(r.charAt(i) == in.charAt(j))
{j++;}
else return false;
else if(r.charAt(k) == '.') {
if(r.charAt(i) == in.charAt(j))
{j++;}
else return false;
while(j< in.length()
&& (r.charAt(i) == in.charAt(j)))
{j++;}
}
i++;
}
else {
int k = i;
if(r.charAt(k) == '*')
while(j< in.length())
{j++;}
else if(r.charAt(k) == '?')
if(j< in.length())
j++;
else if(r.charAt(k) == '+')
{
if(j< in.length()) j++;
else return false;
}
else if(r.charAt(k) == '.')
{
if(j< in.length()) j++;
else return false;
while(j< in.length()){j++;}
}
}
}
if(j< in.length()) return false;
return true;
}
public static void main(String[] args) {
Regex ob = new Regex();
System.out.println(ob.match("aab*d*c*a*b*aa*", "aabbbcbbbaa"));
}
}
No comments:
Post a Comment