java - 匹配多个通配符表达式的最短字符串

Question

我有多个通配符表达式，例如:

*a*b*
*c*d*
*e*?*

哪里

• *表示0个或多个字母(可以是任意字母，不一定相同)
• ? 表示任何一次出现信

我需要找到与这些通配符模式匹配的最短字符串。例如在上面的示例中，这些字符串之一是:

abced

还有另一个例子:

?a*b
a*b*
*a??a*

结果将是

aa?ab -> meaning "aaaab" OR "aabab" OR ...

我想我需要在这里使用动态规划。尝试了一些方法，但只得到了部分结果。有什么想法吗？

Answer 1

适用于较小的示例。对于较大的，需要太多时间。也许是因为我使用数组计算转换。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;

public class Safe {
  public static void main(String[] args) {
    String[] patterns = new String[3];
    patterns[0] = "?a*b";
    patterns[1] = "a*b*";
    patterns[2] = "*a??a*";
    String sol = new Safe().solution(patterns);

    System.out.println(sol);
    if(!sol.equals("aabab")){
      throw new RuntimeException("Not Equal!");
    }

    patterns = new String[3];
    patterns[0] = "*a*b*";
    patterns[1] = "*c*d*";
    patterns[2] = "*e*f*";
    System.out.println(new Safe().solution(patterns));

    patterns = new String[3];
    patterns[0] = "*p?qp?*bd*pd?q*";
    patterns[1] = "*qp*d?b*?p?d*";
    patterns[2] = "?*d?b???q*q?p*";
    sol = new Safe().solution(patterns);

    System.out.println(sol);
    if(!sol.equals("p?qpd?bdpdqqppd")){
      throw new RuntimeException("Not Equal!");
    }

    patterns = new String[2];
    patterns[0] = "*z*y*y*z*x*x*x*z*x*z*y*z*y*x*x*y*y*y*z*x*y*z*y*x*x*x*z*x*z*z*z*y*y*z*x*y*z*";
    patterns[1] = "*y*z*z*x*x*y*z*y*z*y*x*z*y*z*y*x*z*y*x*y*x*y*y*z*x*y*z*x*x*z*y*z*y*y*x*z*y*";

    sol = new Safe().solution(patterns);

    System.out.println(sol);
    if(!sol.equals("yzyyzxxyzyxzyxzyzyxzyxyxyyzxyzyxxxzyxzzzyyxzxyz")){
      throw new RuntimeException("Not Equal!");
    }
  }

  private boolean isItLetter(char c) {
    return c != '*' && c != '?';
  }

  private char match(String[] patterns, int[] indices) {
    boolean firstThrown = true;
    try {
      char matched = '*';
      for (int i = 0; i < patterns.length; i++) {
        char c = patterns[i].charAt(indices[i]);
        firstThrown = false;
        if (isItLetter(c)) {
          if (isItLetter(matched)) {
            if (matched != c) {
              //two different letters
              //so we cannot continue
              return Character.MIN_VALUE;
            }
          }
          matched = c;
        } else {
          //* or ?
          if (!isItLetter(matched)) {
            //so we do not overwrite ? with *
            if (c == '?') {
              matched = c;
            }
          }
        }
      }
      return matched;
    } catch (StringIndexOutOfBoundsException e) {
      //means we tried matching end of string
      //check if all are at the end
      if (firstThrown) {
        //check only if first thrown;
        //otherwise, one of patterns is not at the end
        for (int i = 1; i < patterns.length; i++) {
          if (indices[i] < patterns[i].length()) {
            return Character.MIN_VALUE;
          }
        }
      } else {
        return Character.MIN_VALUE;
      }
      //max when we reached the end
      return Character.MAX_VALUE;
    }
  }

  class Node{
    final String recognized;
    final int[] indices;

    public Node(String recognized, int[] indices) {
      this.recognized = recognized;
      this.indices = indices;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Node node = (Node) o;
      return recognized.equals(node.recognized) &&
          Arrays.equals(indices, node.indices);
    }

    @Override
    public int hashCode() {
      int result = Objects.hash(recognized);
      result = 31 * result + Arrays.hashCode(indices);
      return result;
    }
  }

  Queue<Node> queue = new ArrayDeque<>();
  Set<Node> knownStates = new HashSet<>();

  public String solution(String[] patterns){
    List<int[]> startingIndices = generateStartingIndices(patterns, new int[patterns.length]);

    for(int[] si : startingIndices){
      Node nextNode = new Node("", si);
      queue.offer(nextNode);
    }

    String result = null;
    while (result == null) {
      result = solution(patterns, queue.poll());
    }
    return result;
  }

  private List<int[]> generateStartingIndices(String[] patterns, int[] indices){
    List<int[]> generated = Collections.singletonList(new int[patterns.length]);
    for(int i=0; i<patterns.length; i++){
      char currentChar = patterns[i].charAt(indices[i]);
      List<int[]> replaceGenerated = new ArrayList<>();
      if(currentChar == '*'){
        for(int[] gi : generated){
          gi[i] = indices[i]+1;
          replaceGenerated.add(gi);
        }
        for(int[] gi : generated){
          int[] gin = gi.clone();
          gin[i] = indices[i];
          replaceGenerated.add(gin);
        }
      }
      else{
        for(int[] gi : generated){
          gi[i] = indices[i];
          replaceGenerated.add(gi);
        }
      }
      generated = replaceGenerated;
    }
    return generated;
  }

  private List<int[]> generateNextIndices(String[] patterns, int[] indices){
    List<int[]> generated = Collections.singletonList(new int[patterns.length]);
    for(int i=0; i<patterns.length; i++){
      char currentChar = patterns[i].charAt(indices[i]);
      char nextChar = Character.MIN_VALUE;
      if(indices[i]+1 < patterns[i].length()){
        nextChar = patterns[i].charAt(indices[i]+1);
      }
      List<int[]> replaceGenerated = new ArrayList<>();
      if(currentChar == '*'){
        //or next index
        for(int[] gi : generated){
          gi[i] = indices[i]+1; //short it first so we first test that case
          replaceGenerated.add(gi);
        }
        //same index or
        for(int[] gi : generated){
          int[] gin = gi.clone();
          gin[i] = indices[i];
          replaceGenerated.add(gin);
        }
      }
      else{
        //some character
        if(nextChar=='*'){
          //or if * we can skip
          for(int[] gi : generated){
            gi[i] = indices[i]+2; //skip first so we check that shorter case
            replaceGenerated.add(gi);
          }
        }
        //we can go next or
        for(int[] gi : generated){
          int[] gin = gi.clone();
          gin[i] = indices[i]+1;
          replaceGenerated.add(gin);
        }
      }
      generated = replaceGenerated;
    }
    return generated;
  }

  public String solution(String[] patterns, Node node) {
    char matched = match(patterns, node.indices);

    if (matched == Character.MAX_VALUE) {
      //we reached the end
      return node.recognized;
    }
    if (matched == Character.MIN_VALUE) {
      //impossible to match
      return null;
    }
    if(matched == '*'){
      //all stars
      return null;
    }

    List<int[]> nextIndices = generateNextIndices(patterns, node.indices);

    for(int[] ni : nextIndices){
        Node nextNode = new Node(node.recognized + matched, ni);
        if(notKnownState(nextNode)) {
          queue.offer(nextNode);
        }
    }

    return null;
  }

  private boolean notKnownState(Node node) {
    if(knownStates.contains(node)){
      return false;
    }
    knownStates.add(node);
    return true;
  }
}