java - 是否有更好的方法来分析作为示例给出的输入/输出数组之间的路径？

Question

下面显示的示例是我目前正在进行的信号路径分析的简化版本。对于输入数组 (iArray) 中的每个索引，在同一索引处都有一个输出 (oArray)。正如您在结果中看到的那样，递归调用将具有重复的分析路径，这些路径并不重要(如结果所示)。问题是是否有更好(即更快)的分析解决方案？

代码:

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {

    private static String[] iArray = new String[]{
        "a","a","a","b","b","b","b","b","c","c","c","c",
          "d","d","d","d","e","e","e","e","f","f","g","g","g","g",
            "h","h","k","l","l","m","n","n","n","n","n","o","o",
              "s","s","s","s","s","s"};

    private static String[] oArray = new String[]{
        "b","c","d","e","f","g","h","i","d","f","h","l","j","a","n",
          "s","a","f","g","i","s","b","b","n","a","c","i","j","e","s",
            "b","b","o","d","s","a","b","b","s","a","j","l","o","n","k"};

    public static void recPathAnalysis(String signal, int level, String path) {
        if (level < 10) {
            for (int i = 0; i < iArray.length; i++) {
                if (signal.equals(iArray[i])) {
                    if (!path.contains(oArray[i])) {
                        System.out.println("normal >> " + path + " " + oArray[i]);              
                        recPathAnalysis(oArray[i], level + 1 ,  path + " " + oArray[i]);
                    } else {
                        System.out.println("loop   >> " + path + " " + oArray[i]);              
                    }
                }
            }
        }
}

    public static void main (String[] args) {
        recPathAnalysis("a", 0, "a");
    }
}

结果:

    normal >> a b            **not needed**
    normal >> a b e          **not needed**
    loop   >> a b e a
    normal >> a b e f        **not needed**
    normal >> a b e f s      **not needed** 
    loop   >> a b e f s a
    normal >> a b e f s j
    normal >> a b e f s l    **not needed**
    loop   >> a b e f s l s
    loop   >> a b e f s l b
    normal >> a b e f s o    **not needed**
    loop   >> a b e f s o b
    loop   >> a b e f s o s
    normal >> a b e f s n    **not needed**
    normal >> a b e f s n o
    ....

Answer 1

这里使用的数据结构可以做一个小的改进，而不是 public static void recPathAnalysis(String signal, int level, String path) , public static void recPathAnalysis(String signal, int level, HashSet<Character> path)可以使用。由于您使用 if (!path.contains(oArray[i]))复杂度为 O(n)，但如果你使用 HashSet 则为 O(1)。可以获得轻微的性能提升。