Advertisement
vladimirVenkov

Wildcards44.

Jun 16th, 2018
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.75 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. public class WildcardMatching44Leet {
  6.     public static void main(String[] args) throws IOException {
  7.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8.  
  9.         String one = br.readLine();
  10.         String two = br.readLine();
  11.         //System.out.println(isSame(one, two));
  12.  
  13.         System.out.println(isMatch(one, two));
  14.  
  15.     }
  16.  
  17.     static int goNextChar(String input) {
  18.         for (int i = 0; i < input.length(); i++) {
  19.             char temp = input.charAt(i);
  20.             if (Character.isAlphabetic(temp)) {
  21.                 return i;
  22.             }
  23.         }
  24.         return - 1;
  25.     }
  26.  
  27.     static boolean compare(String inp, String expr) {
  28.         if(inp.length() == 0 && expr.length() == 0) return true;
  29.         int counter = 0;
  30.         for (int i = 0; i < expr.length(); i++) {
  31.             if(expr.charAt(i)== '?') counter ++;
  32.             }
  33.             if(counter == inp.length()) return true;
  34.             else if (counter > inp.length()) return false;
  35.             if(expr.contains("*")) return true;
  36.  
  37.             return false;
  38.     }
  39.  
  40.     static boolean ifEquals(String inp, String expr) {
  41.         if(inp.equals(expr)) return true;
  42.         return false;
  43.     }
  44.  
  45.     static boolean isSame(String inp, String expr) {
  46.         int indexNextChar = goNextChar(expr);
  47.         if (indexNextChar < 0 ) {
  48.             return compare(inp, expr);
  49.         }
  50.         char nextChar = expr.charAt(indexNextChar);
  51.         for (int i = 0; i < inp.length(); i++) {
  52.             if (inp.charAt(i) == nextChar) {
  53.                 if(isSame(inp.substring(0,i),
  54.                         expr.substring(0, indexNextChar))
  55.                     &&
  56.                 isSame(trimarator(inp, i + 1 , inp.length()),
  57.                         trimarator(expr, indexNextChar + 1, expr.length()))) return true;
  58.             }
  59.         }
  60.         return false;
  61.     }
  62.  
  63.     static String trimarator(String word, int inOne, int twoInd) {
  64.         if (inOne >= twoInd || inOne < 0 ) return "";
  65.         return word.substring(inOne,twoInd);
  66.     }
  67.  
  68.     public static boolean isMatch(String s, String p) {
  69.         boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
  70.         dp[0][0] = true;
  71.  
  72.         for (int i = 0; i <= s.length(); i++){
  73.             for (int j = 1; j <= p.length(); j++){
  74.                 if (p.charAt(j - 1) == '*'){
  75.                     dp[i][j] = i > 0 && dp[i - 1][j] || dp[i][j - 1];
  76.                 } else{
  77.                     dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
  78.                 }
  79.             }
  80.         }
  81.  
  82.         return dp[s.length()][p.length()];
  83.     }
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement