import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Main {
    private static final String STAR = "*";
    private static final String CHAR = "?";

    private final List<String> pattern;

    public Main(final String pattern) {
        this.pattern = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (char c: pattern.toCharArray()) {
            final String token;
            switch (c) {
                case '*':
                    token = STAR;
                    break;
                case '?':
                    token = CHAR;
                    break;
                default:
                    token = null;
                    break;
            }
            if (token == null) {
                sb.append(c);
            } else {
                if (sb.length() > 0) {
                    this.pattern.add(sb.toString());
                    sb.setLength(0);
                }
                this.pattern.add(token);
            }
        }
        if (sb.length() > 0) {
            this.pattern.add(sb.toString());
        }
        ListIterator<String> iter = this.pattern.listIterator();
        while (iter.hasNext()) {
            if (iter.next() == STAR) {
                if (iter.hasNext()) {
                    String next = iter.next();
                    if (next == STAR) {
                        iter.remove();
                        iter.previous();
                    } else if (next == CHAR) {
                        iter.set(STAR);
                        iter.previous();
                        iter.previous();
                        iter.set(CHAR);
                        iter.next();
                    }
                }
            }
        }
    }

    private boolean match(int pos, final String str) {
        if (pos == pattern.size()) {
            return str.isEmpty();
        } else {
            String token = pattern.get(pos++);
            if (token == STAR) {
                if (pos == pattern.size()) {
                    return true;
                } else {
                    // this must be a non-wildcard token
                    token = pattern.get(pos++);
                    int length = token.length();
                    for (int idx = str.indexOf(token); idx != -1;
                        idx = str.indexOf(token, idx + 1))
                    {
                        if (match(pos, str.substring(idx + length))) {
                            return true;
                        }
                    }
                }
            } else if (token == CHAR) {
                if (!str.isEmpty()) {
                    return match(pos, str.substring(1));
                }
            } else {
                if (str.startsWith(token)) {
                    return match(pos, str.substring(token.length()));
                }
            }
            return false;
        }
    }

    public boolean match(final String str) {
        return match(0, str);
    }

    @Override
    public String toString() {
        return pattern.toString();
    }

    public static void main(final String[] args) {
        System.out.println(new Main("hello*world").match("helloworld"));
        System.out.println(new Main("hello*world").match("hello, world"));
        System.out.println(!(new Main("hello?*world").match("helloworld")));
        System.out.println(new Main("hello?*world").match("hello world"));
        System.out.println(new Main("hello*?world").match("hello, world"));
        System.out.println(!(new Main("hello*?*?world").match("hello world")));
        System.out.println(new Main("hello*?*?world").match("hello, world"));
        System.out.println(!(new Main("hello*??*world").match("hello, world!")));
        System.out.println(new Main("hello*?**?").match("hello!!"));
        System.out.println(!(new Main("hello*?**?").match("hello!")));
        System.out.println(new Main("*?*?hello").match("world, hello"));
        System.out.println(!(new Main("*?*?hello").match(" hello")));
        System.out.println(new Main("*a").match("aaa"));
    }
}