fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.ListIterator;
  4.  
  5. public class Main {
  6.     private static final String STAR = "*";
  7.     private static final String CHAR = "?";
  8.  
  9.     private final List<String> pattern;
  10.  
  11.     public Main(final String pattern) {
  12.         this.pattern = new ArrayList<>();
  13.         StringBuilder sb = new StringBuilder();
  14.         for (char c: pattern.toCharArray()) {
  15.             final String token;
  16.             switch (c) {
  17.                 case '*':
  18.                     token = STAR;
  19.                     break;
  20.                 case '?':
  21.                     token = CHAR;
  22.                     break;
  23.                 default:
  24.                     token = null;
  25.                     break;
  26.             }
  27.             if (token == null) {
  28.                 sb.append(c);
  29.             } else {
  30.                 if (sb.length() > 0) {
  31.                     this.pattern.add(sb.toString());
  32.                     sb.setLength(0);
  33.                 }
  34.                 this.pattern.add(token);
  35.             }
  36.         }
  37.         if (sb.length() > 0) {
  38.             this.pattern.add(sb.toString());
  39.         }
  40.         ListIterator<String> iter = this.pattern.listIterator();
  41.         while (iter.hasNext()) {
  42.             if (iter.next() == STAR) {
  43.                 if (iter.hasNext()) {
  44.                     String next = iter.next();
  45.                     if (next == STAR) {
  46.                         iter.remove();
  47.                         iter.previous();
  48.                     } else if (next == CHAR) {
  49.                         iter.set(STAR);
  50.                         iter.previous();
  51.                         iter.previous();
  52.                         iter.set(CHAR);
  53.                         iter.next();
  54.                     }
  55.                 }
  56.             }
  57.         }
  58.     }
  59.  
  60.     private boolean match(int pos, final String str) {
  61.         if (pos == pattern.size()) {
  62.             return str.isEmpty();
  63.         } else {
  64.             String token = pattern.get(pos++);
  65.             if (token == STAR) {
  66.                 if (pos == pattern.size()) {
  67.                     return true;
  68.                 } else {
  69.                     // this must be a non-wildcard token
  70.                     token = pattern.get(pos++);
  71.                     int length = token.length();
  72.                     for (int idx = str.indexOf(token); idx != -1;
  73.                         idx = str.indexOf(token, idx + 1))
  74.                     {
  75.                         if (match(pos, str.substring(idx + length))) {
  76.                             return true;
  77.                         }
  78.                     }
  79.                 }
  80.             } else if (token == CHAR) {
  81.                 if (!str.isEmpty()) {
  82.                     return match(pos, str.substring(1));
  83.                 }
  84.             } else {
  85.                 if (str.startsWith(token)) {
  86.                     return match(pos, str.substring(token.length()));
  87.                 }
  88.             }
  89.             return false;
  90.         }
  91.     }
  92.  
  93.     public boolean match(final String str) {
  94.         return match(0, str);
  95.     }
  96.  
  97.     @Override
  98.     public String toString() {
  99.         return pattern.toString();
  100.     }
  101.  
  102.     public static void main(final String[] args) {
  103.         System.out.println(new Main("hello*world").match("helloworld"));
  104.         System.out.println(new Main("hello*world").match("hello, world"));
  105.         System.out.println(!(new Main("hello?*world").match("helloworld")));
  106.         System.out.println(new Main("hello?*world").match("hello world"));
  107.         System.out.println(new Main("hello*?world").match("hello, world"));
  108.         System.out.println(!(new Main("hello*?*?world").match("hello world")));
  109.         System.out.println(new Main("hello*?*?world").match("hello, world"));
  110.         System.out.println(!(new Main("hello*??*world").match("hello, world!")));
  111.         System.out.println(new Main("hello*?**?").match("hello!!"));
  112.         System.out.println(!(new Main("hello*?**?").match("hello!")));
  113.         System.out.println(new Main("*?*?hello").match("world, hello"));
  114.         System.out.println(!(new Main("*?*?hello").match(" hello")));
  115.         System.out.println(new Main("*a").match("aaa"));
  116.     }
  117. }
Success #stdin #stdout 0.07s 215552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
true
true
true
true
true
true
true
true
true
true
true
true
https://ideone.com/0x8GLp
language:
Java (12.0.1)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!