查找字符串中置换的索引

Question

null

dog cat rat
abcratdogcattgh
3

其中3是结果（由system.out打印）。

在列表中有重复的单词是合法的：

dog cat rat cat
abccatratdogzzzzdogcatratcat
16

我生成的代码可以工作，前提是答案开头的单词以前没有出现过。在这里的第二个示例中，我的代码将失败，因为dog已经出现在答案从索引16开始的地方。

null

下面是我的代码（应该是可编译的）：

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();
        String[] l = line.split(" ");
        String s = br.readLine();

        int wl = l[0].length();
        int len = wl * l.length;
        int sl = s.length();

        for (String word : l) {
            int i = s.indexOf(word);
            int z = i;
            //while (i != -1) {
                int y = i + len;
                if (y <= sl) {
                    String sub = s.substring(i, y);
                    if (containsAllWords(l, sub)) {
                        System.out.println(s.indexOf(sub));
                        System.exit(0);
                    }
                }
                //z+= wl;
                //i = s.indexOf(word, z);
            //}
        }
        System.out.println("-1");
    }

    private static boolean containsAllWords(String[] l, String s) {
        String s2 = s;

        for (String word : l) {
            s2 = s2.replaceFirst(word, "");
        }

        if (s2.equals(""))
            return true;
        return false;
    }
}

我可以通过取消注释while循环来解决我的问题，并使其通过第二个示例。然而，这会对性能产生严重影响。当我们输入100个单词、每个10个字符和1000000个字符的字符串时，完成所需的时间非常糟糕。

假定测试台中的每个案例都有一个最大执行时间，添加while循环将导致测试在没有及时完成执行的基础上失败。

Answer 1

如果将字符串连接在一起并使用要搜索的新字符串。

String a = "dog"
String b = "cat"
String c = a+b; //output of c would be "dogcat"

这样你就可以克服狗在某处出现的问题。

但是如果catdog也是一个有效值，这就不起作用了。