Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1181.html

1181. Before and After Puzzle

Level

Medium

Description

Given a list of phrases, generate a list of Before and After puzzles.

A phrase is a string that consists of lowercase English letters and spaces only. No space appears in the start or the end of a phrase. There are no consecutive spaces in a phrase.

Before and After puzzles are phrases that are formed by merging two phrases where the last word of the first phrase is the same as the first word of the second phrase.

Return the Before and After puzzles that can be formed by every two phrases phrases[i] and phrases[j] where i != j. Note that the order of matching two phrases matters, we want to consider both orders.

You should return a list of distinct strings sorted lexicographically.

Example 1:

Input: phrases = ["writing code","code rocks"]
Output: ["writing code rocks"]

Example 2:

Input: phrases = ["mission statement",
                  "a quick bite to eat",
                  "a chip off the old block",
                  "chocolate bar",
                  "mission impossible",
                  "a man on a mission",
                  "block party",
                  "eat my words",
                  "bar of soap"]
Output: ["a chip off the old block party",
         "a man on a mission impossible",
         "a man on a mission statement",
         "a quick bite to eat my words",
         "chocolate bar of soap"]

Example 3:

Input: phrases = ["a","b","a"]
Output: ["a"]

Constraints:

  • 1 <= phrases.length <= 100
  • 1 <= phrases[i].length <= 100

Solution

The basic idea is to use a map to store each word and the phrases that start with the word. For each phrase in phrases, obtain its first word, and add the current phrase to the list of the first word. Then for each phrase in phrases, obtain the last word of phrase and the phrases whose first words equal the current last word, and merge the current phrase with each of the next phrases to form new phrases.

There is one point that needs to be considered. If a phrase from phrases has the same first word and last word (for example, any phrase that has only one word, or phrases like "a b a"), then the phrase can’t be merged with itself since the two phrases must have different indices. If there are several elements in phrases that have the same content as phrase, then they can be merged. To solve this, use another map to store each phrase and the number of occurrences of the phrase in phrases. If a phrase that has the same first word and last word is met, merge it with itself if and only if the number of occurrences of the phrase in phrases is greater than 1.

Since a set does not contain duplicates, use a set to store the new phrases formed by merging phrases. Finally, create a list from the set, sort the list and return.

  • class Solution {
    public List<String> beforeAndAfterPuzzles(String[] phrases) {
        Map<String, Integer> countMap = new HashMap<String, Integer>();
        Map<String, Set<String>> firstMap = new HashMap<String, Set<String>>();
        for (String phrase : phrases) {
            int count = countMap.getOrDefault(phrase, 0) + 1;
            countMap.put(phrase, count);
            int spaceIndex = phrase.indexOf(' ');
            String first = spaceIndex >= 0 ? phrase.substring(0, spaceIndex) : phrase;
            Set<String> firstSet = firstMap.getOrDefault(first, new HashSet<String>());
            firstSet.add(phrase);
            firstMap.put(first, firstSet);
        }
        Set<String> set = new HashSet<String>();
        for (String phrase : phrases) {
            int lastSpaceIndex = phrase.lastIndexOf(' ');
            String last = lastSpaceIndex >= 0 ? phrase.substring(lastSpaceIndex + 1) : phrase;
            String prefix = lastSpaceIndex >= 0 ? phrase.substring(0, lastSpaceIndex + 1) : "";
            Set<String> firstSet = firstMap.getOrDefault(last, new HashSet<String>());
            for (String nextStr : firstSet) {
                if (nextStr.equals(phrase)) {
                    int count = countMap.getOrDefault(nextStr, 0);
                    if (count > 1) {
                        String newStr = prefix + nextStr;
                        set.add(newStr);
                    }
                } else {
                    String newStr = prefix + nextStr;
                    set.add(newStr);
                }
            }
        }
        List<String> puzzlesList = new ArrayList<String>(set);
        Collections.sort(puzzlesList);
        return puzzlesList;
    }
}

  • class Solution:
    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
        same_first_word = defaultdict(set)
        for i, phrase in enumerate(phrases):
            same_first_word[phrase.split()[0]].add(i)
        res = set()
        for i, phrase in enumerate(phrases):
            words = phrase.split()
            last_word = words[-1]
            if last_word in same_first_word:
                for j in same_first_word[last_word]:
                    if i != j:
                        res.add(' '.join(words[:-1] + phrases[j].split()))
        return sorted(list(res))

All Problems

All Solutions