recursive solution in Java


  • 0
    J

    it's not as concise as the most popular one, but seems easier to understand.

    enum Kind {FULL, PREFIX, SURFIX, MIDDLE};
    
      public boolean isMatch(String str, String pattern) {
        String[] ss = pattern.split("\\*");
        ArrayList<String> ps = new ArrayList<>();
        for (String s : ss) {
            if (!s.isEmpty()) ps.add(s);
        }
        boolean startsWithWildCard = pattern.startsWith("*");
        boolean endsWithWildCard = pattern.endsWith("*");
        Kind kind = startsWithWildCard ? (endsWithWildCard ? Kind.MIDDLE : Kind.SURFIX) : (endsWithWildCard ? Kind.PREFIX : Kind.FULL);
        return match(str, 0, str.length() - 1, ps, 0, ps.size() - 1, kind);
      }
    
      private boolean match(String s, int s1, int e1, ArrayList<String> patterns, int s2, int e2, Kind kind) {
        if (s1 > e1) return (s2 > e2);
        if (s2 > e2) return kind == Kind.PREFIX || kind == Kind.MIDDLE;
        switch (kind) {
          case FULL: return matchPart(s, s1, e1, patterns.get(s2), true) && match(s, s1 + patterns.get(s2).length(), e1, patterns, s2 + 1, e2, Kind.SURFIX);
          case PREFIX: return matchPart(s, s1, e1, patterns.get(s2), true) && match(s, s1 + patterns.get(s2).length(), e1, patterns, s2 + 1, e2, Kind.MIDDLE);
          case SURFIX: return matchPart(s, s1, e1, patterns.get(e2), false) && match(s, s1, e1 - patterns.get(e2).length(), patterns, s2, e2 -1, Kind.MIDDLE);
          case MIDDLE: 
              int idx = indexOf(s, s1, e1, patterns.get(s2));
              return idx >= s1 && idx <= e1 && match(s, idx + patterns.get(s2).length(), e1, patterns, s2 + 1, e2, Kind.MIDDLE);
        }
        return false;
      }
    
      private boolean matchPart(String str, int s, int e, String p, boolean forward) {
        if (e - s + 1< p.length()) return false;
        for (int i = 0; i < p.length(); i++) {
          int idx = forward ? s + i : e - p.length() + i + 1;
          if (str.charAt(idx) != p.charAt(i) && p.charAt(i) != '?') return false;
        }
        return true;
      }
      
      private int indexOf(String str, int s, int e, String p) {
        for (int i = s; i <= e; i++) {
          if (e - i + 1 < p.length()) return -1;
          int j = 0;
          for (; j < p.length(); j++) {
            if (str.charAt(i + j) != p.charAt(j) && p.charAt(j) != '?') break;
          }
          if (j == p.length()) return i;
        }
        return -1;
      }
    

  • 0
    J

    indexOf(...) matchPart(...) are dummy helper functions.
    basical idea is simple.

    1. split pattern on wild cards into list of strings.
    2. pattern list either is prefix, surfix, in the middle or exact.

    the logic is pretty simple. though code is longer, it's easier to understand


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.