java - 具有两个列表的最小连续子序列

Question

TargetList 和AvailableTagsList 是两个字符串列表。 TargetList 将包含不同的字符串对象。

Input:
TargetList = {"cat", "dog"};
AvailableTagsList = {"cat", "test", "dog", "get", "spain", "south"};
Output: [0, 2] //'cat' in position 0; 'dog' in position 2


Input:
TargetList = {"east", "in", "south"};
AvailableTagsList = {"east", "test", "east", "in", "east", "get", "spain", "south"};
Output: [2, 7] //'east' in position 2; 'in' in position 3; 
              //'south' in position 6 (east in position 4 is not outputted as it is coming after 'in')

Input:
TargetList = {"east", "in", "south"};
AvailableTagsList = {"east", "test", "south"};
Output: [0] //'in' not present in availableTagsList

我将单词在 AvailableTags 中出现的位置存储到 listMap 中。

Map<String, List<Integer>> listMap = new HashMap<>();
int counter = 0;
for(String availableItem : AvailableTagsList) 
{
    if(listMap.containsKey(availableItem))
        listMap.get(availableItem).add(counter);
    else 
    {
        List<Integer> temp = new ArrayList<>();
        temp.add(counter);
        listMap.put(availableItem, temp);
    }
    counter++;
}

然后我将 listMap 中的所有元素列表添加到 resultList。

listMap will be like 
"east" - [0,2,4] 
"in" - [3] 
"south" - [7] 

resultList will have like [0,2,4,3,7] 

我无法解决的问题是，使用此 resultList 如何在 AvailableTagsList 中显示最小子序列？我使用的方法正确吗？目前我的进展如何？是否有任何其他替代方法可以解决此问题。

Answer 1

我不知道这个问题的最佳解决方案，但根据你的想法

• 从 TargetList 中获取每个单词在 AvailableTagsList(请注意，它们将被排序)例如，如果我 目标列表和可用列表是:TargetList = {"east", "in", “南”} AvailableTagsList = {“东”，“测试”，“东”，“中”，“东”， "get", "spain", "south"} 所以在这一步之后我会向东: 0,2,4 in : 3 南:7
• 现在:我知道我可以有 3 个可能的开始，对吗？为了第一 我的起始词 p0 的位置，我能找到一个词的位置 p1 吗 (i+1) 这样 p1 > p0 ??如果是的话，我可以有一个职位 p2 吗 word(i+2) 这样 p2 > p1 等等，直到我找到我所有的目标列表。 我怎样才能做到这一点 ？如果我知道位置 p1 ，我需要找到 首先 p2 这样 p2 > p1 ？我可以使用二进制搜索来做到这一点吗？ 是的，因为所有数组都已排序。所以这是代码

public class MinimumCtsSubsequence {

    static String[] words, tags;

    public static void main(String[] args) {
        words = new String[] { "east", "in", "south" };
        tags = new String[] { "east", "test", "east", "in", "east", "get", "spain", "south" };
        ArrayList<Integer> ans = minSubSequence();
        for (int i = 0; i < ans.size(); ++i) {
            System.out.print(ans.get(i) + " ");
        }

    }

    static ArrayList<Integer> minSubSequence() {
        ArrayList<Integer>[] occur = new ArrayList[words.length];
        for (int i = 0; i < words.length; ++i)
            occur[i] = new ArrayList<Integer>();
        HashMap<String, Integer> indices = new HashMap<String, Integer>();
        for (int i = 0; i < words.length; ++i) {
            indices.put(words[i], i);
        }
        for (int i = 0; i < tags.length; ++i) {
            String tag = tags[i];
            if (indices.containsKey(tag)) {
                int wordI = indices.get(tag);
                occur[wordI].add(i);
            }
        }
        // till now comp is o(n)
        // loop throught all the starts that we have
        int ans = Integer.MAX_VALUE;
        int s1 = 0, e1 = 0;
        for (int i = 0; i < occur[0].size(); ++i) {
            int start = occur[0].get(i);
            boolean poss = true;
            int next = 0;
            for (int j = 1; j < words.length; ++j) {
                next = getNextGreater(start, occur[j]);
                if (next == -1) {
                    poss = false;
                    break;
                }
            }
            if (poss && ans > next - start) {
                s1 = start;
                e1 = next;
                ans = next - start;
            }

        }
        ArrayList<Integer> solu = new ArrayList<Integer>();

        if (ans == Integer.MAX_VALUE) {
            solu.add(0);
            return solu;
        }

        solu.add(s1);
        solu.add(e1);

        return solu;
    }

    static int getNextGreater(int x, ArrayList<Integer> arr) {
        int start = 0;
        int end = arr.size() - 1;
        int ans = -1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (arr.get(mid) <= x) {// go right
                start = mid + 1;
            } else {
                ans = arr.get(mid);
                end = mid;
            }

        }
        if (start == end && arr.get(start) > x)
            return arr.get(start);
        return ans;
    }