如何高效求解匹配目标数字子序列的最短合法生成序列？

任务说明 #

某电脑存储的特殊数字由firstStep和secondStep通过游戏生成，部分数字丢失后得到puzzleNumber。需要找出能通过删除部分字符得到puzzleNumber的最短完整序列，若不存在则返回"-1"。

游戏规则 #

• 初始分数为0，每次操作可给当前分数加上firstStep或secondStep
• 每次操作后，记录当前分数的个位数字，所有记录的数字按顺序组成完整序列

约束条件 #

• 2 ≤ |puzzleNumber| ≤ 2×10^5
• 1 ≤ firstStep, secondStep ≤ 9

示例 #

当puzzleNumber="27"，firstStep=2，secondStep=3时，最短序列为"247"。

问题求助 #

本人编写的BFS代码仅通过7/15测试用例，存在错误和超时问题，现咨询时间复杂度更优的正确解法。

原代码如下：

import java.util.*;

public class Main {
    public static String solve(String puzzleNumber, int firstStep, int secondStep) {
        Queue<State> queue = new LinkedList<>();
        Set<String> seen = new HashSet<>();

        queue.offer(new State(0, "", 0)); // cur, sequence, matchedIndex

        while (!queue.isEmpty()) {
            State curr = queue.poll();

            if (curr.matched == puzzleNumber.length()) {
                return curr.sequence;
            }

            String key = (curr.cur % 10) + ":" + curr.matched;
            if (seen.contains(key)) continue;
            seen.add(key);

            // Try adding firstStep
            int nextX = curr.cur + firstStep;
            int digitX = nextX % 10;
            int matchedX = curr.matched;
            if (matchedX < puzzleNumber.length() && puzzleNumber.charAt(matchedX) == (char)(digitX + '0')) {
                matchedX++;
            }
            queue.offer(new State(nextX, curr.sequence + digitX, matchedX));

            // Try adding secondStep
            if (firstStep != secondStep) { // prevent duplicate branches
                int nextY = curr.cur + secondStep;
                int digitY = nextY % 10;
                int matchedY = curr.matched;
                if (matchedY < puzzleNumber.length() && puzzleNumber.charAt(matchedY) == (char)(digitY + '0')) {
                    matchedY++;
                }
                queue.offer(new State(nextY, curr.sequence + digitY, matchedY));
            }
        }

        return "-1";
    }

    static class State {
        int cur;
        String sequence;
        int matched;

        State(int cur, String sequence, int matched) {
            this.cur = cur;
            this.sequence = sequence;
            this.matched = matched;
        }
    }

    public static void main(String[] args) {
        System.out.println(solve("27", 2, 3)); // Expected output: "247"
        System.out.println(solve("324", 2, 3)); // Expected: 36924
        System.out.println(solve("521", 5, 5)); // Expected: -1    
    }
}

内容的提问来源于stack exchange，提问作者CodeCrusader