java - "Before and After"谜题有更好的解决方案吗？

Question

这是我针对新毕业生软件工程师职位面试的 Hackerrank 编码挑战:

拼图之前和之后

给定一个短语列表，生成一个命运之轮“之前和之后”谜题列表。 “之前和之后”谜题是指一个短语以另一个短语的第一个单词的最后一个单词结尾的情况。作为一个基本示例，给定两个短语“writing code”和“coderocks”，输出将是“writing coderocks”。这是输入和预期输出的更全面的示例。

输入 = [ “使命声明”， “快点吃点东西”， “一个模子出来的”， “巧克力吧”， “不可能完成的任务”， “一个肩负使命的人”， “区 block 党”， “吃掉我的话”， “一 block 肥皂”]

输出 = [ “快点吃掉我的话”， “旧街区派对的一小部分”， “巧克力肥皂”， “一个有使命声明的人”， “一个执行不可能任务的人”]

限制:- 返回的结果不必是唯一的- 不用担心外壳。假设输入只是 a - z 带空格的小写字母(因此没有特殊字符或处理大小写匹配的单词)- 假设所有空白都是单个空格(无需担心空白间距边缘情况)

我通过完成 6/7 个测试用例解决了这个问题，其中最后一个测试用例由于超时而终止。

// 1. Submitted code during the interview (cleared 6/7 test-cases) 

/*
My approach: Compare every phrase in the list to every other phrase in the list.
If the last word of the phrase matches the first word of another phrase, do the
following: 
1) Remove the first word from the other phrase.
2) Combine both phrases
3) Add the combined phrase to the output list.
*/

private static List<String> generate_phrases(List<String> phrases) {
        List<String> output = new ArrayList<>();
        for(String temp: phrases) {
            String[] content = temp.split(" ");
            for(String temp2: phrases) {
                String[] content2 = temp2.split(" ");
                if(content[content.length-1].equals(content2[0])) {
                    String tempWord = content2[0];
                    temp2 = temp2.replaceAll(tempWord, "");
                    output.add(temp+temp2);
                }
            }
        }
        return output;
    }

// 2. Improved code after the interview

/* 
My approach: Compare every phrase in the list to every other phrase in the list.
If the last word of the phrase matches the first word of another phrase, do the
following: 
1) Push both phrases to a set.
2) Remove the first word from the other phrase.
3) Combine both phrases
4) Add the combined phrase to the output list.
5) for all phrases added in the set, decrease the size of the input list by removing the visited phrases
*/

private static List<String> generate_phrases(List<String> phrases) {
        List<String> output = new ArrayList<>(); boolean flag = false;
        int length = phrases.size();
        for(int i=0; i<length; i++) {
            Set<String> wordsToRemove = new HashSet<>();
            String temp = phrases.get(i);
            String[] contents1 = temp.split(" ");
            for(int j=0; j<length; j++) {
                String temp2 = phrases.get(j);
                String[] contents2 = temp2.split(" ");
                if(contents1[contents1.length-1].equals(contents2[0])) {
                    flag = true;
                    wordsToRemove.add(temp); wordsToRemove.add(temp2);
                    String tempWord = contents2[0];
                    temp2 = temp2.replaceAll(tempWord, "");
                    output.add(temp+temp2);
                }
            }
            if(flag) {
                for (String s : wordsToRemove){ phrases.remove(s); length--; }
                flag = false; i=0;
            }
        }
        return output;
    }

我提交了第一段代码，但最后一个测试用例失败并因超时而终止。这是我在面试过程中能做的最好的事情。面试后花了一些时间，我想出了一个有效的解决方案，比之前的迭代次数更少。但我所有的解决方案都使用 2 个 for 循环。有人可以帮助我编写更好、更高效的代码吗？

按照我帖子中评论中的方法，我想出了一个解决方案。但还是不知道这样是否会更有效率。现在我的代码的时间复杂度是多少？

public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("mission statement");
        list.add("a quick bite to eat");
        list.add("a chip off the old block");
        list.add("chocolate bar");
        list.add("mission impossible");
        list.add("a man on a mission");
        list.add("block party");
        list.add("eat my words");
        list.add("bar of soap");
        System.out.println(generate_phrases(list));
    }

private static List<String> generate_phrases(List<String> phrases) {
        List<Phrase> phraseList = generatePhraseList(phrases);
        Map<String, List<Phrase>> map = generateHashMapOfUniqueKeys(phraseList);
        return generateOutputList(map);
    }

    private static List<Phrase> generatePhraseList(List<String> phrases) {
        List<Phrase> phraseList = new ArrayList<>();
        for (String p: phrases) {
            Phrase temp = new Phrase(p);
            phraseList.add(temp);
        }
        return phraseList;
    }

    private static Map<String, List<Phrase>> generateHashMapOfUniqueKeys(List<Phrase> phraseList) {
        Map<String, List<Phrase>> map = new HashMap<>();
        for(Phrase p : phraseList) {
            String start = p.getStart();
            if(!map.containsKey(start)) {
                List<Phrase> temp = new ArrayList<>();
                temp.add(p);
                map.put(start, temp);
            } else {
                map.get(start).add(p);
            }
        }
        return map;
    }

    private static List<String> generateOutputList(Map<String, List<Phrase>> map) {
        List<String> output = new ArrayList<>();
        for(List<Phrase> list: map.values()) {
            for(Phrase p: list) {
                String keyToBeSearched = p.getEnd();
                if(map.containsKey(keyToBeSearched)) {
                    List<Phrase> temp = map.get(keyToBeSearched);
                    for(Phrase p2: temp) {
                        output.add(p.getWhole()+" "+p2.getMiddle());
                    }
                }
            }
        }
        return output;
    }

}

class Phrase {
    private final String start;
    private final String middle;
    private final String end;
    private final String whole;

    public Phrase(String initial) {
        this.whole = initial;
        String[] words = initial.split(" ");
        this.start = words[0];
        this.middle = Arrays.stream(words, 1, words.length).collect(joining(" "));
        this.end = words[words.length - 1];
    }

    public String getStart() {
        return this.start;
    }

    public String getMiddle() {
        return this.middle;
    }

    public String getEnd() {
        return this.end;
    }

    public String getWhole() {
        return this.whole;
    }

}

Answer 1

可能值得封装收集拆分操作的结果，以便不需要多次重复:

class Phrase {
    private final String start;
    private final String middle;
    private final String end;

    public Phrase(String initial) {
        String[] words = initial.split(" ");
        start = words[0];
        middle = Arrays.stream(words, 1, words.length).collect(joining(" "));
        end = words[words.length - 1];
    }

    public boolean matches(Phrase other) {
        this.end.equals(other.start);
    }

    public String combine(Phrase other) {
        assert matches(other);
        return Stream.of(this.start, this.middle, this.end, other.middle, other.end)
            .collect(joining(" "));
    }
}

然后你的生成代码就变得非常简单:

List<Phrase> phrases = Arrays.stream(inputPhrases).map(Phrase::new).collect(toList());
return phrases.stream()
    .flatMap(ph1 -> phrases.stream().filter(ph1::matches).map(ph1::combine))
    .collect(toList());

我不确定这是否更有效，但我的猜测是，对于小输入，它的效率会较低，而对于大输入，它的效率会更高。如果您的硬件可以利用多个执行线程，您还可以使流并行以利用多个执行线程。