Before and After Puzzle

Problem

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.

Examples

Example 1:

1
2


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

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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:

1
2


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

Constraints:

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

Solution

Method 1 – Hash Map for First and Last Word Matching

Intuition

To form a before and after puzzle, we need to efficiently find all pairs of phrases where the last word of one matches the first word of another. Using hash maps to group phrases by their first and last words allows us to quickly generate all valid combinations.

Approach

For each phrase, extract its first and last word.
Build a mapping from first word to all phrases starting with that word, and from last word to all phrases ending with that word.
For each phrase, find all phrases whose first word matches its last word (excluding itself).
Merge the two phrases by removing the duplicate word in the middle.
Store all unique results in a set.
Return the sorted list of results.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
public:
    vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
        unordered_map<string, vector<int>> first, last;
        int n = phrases.size();
        for (int i = 0; i < n; ++i) {
            stringstream ss1(phrases[i]);
            string fw, lw, w;
            ss1 >> fw;
            while (ss1 >> w) lw = w;
            if (lw.empty()) lw = fw;
            first[fw].push_back(i);
            last[lw].push_back(i);
        }
        set<string> ans;
        for (int i = 0; i < n; ++i) {
            stringstream ss1(phrases[i]);
            string fw, lw, w;
            ss1 >> fw;
            while (ss1 >> w) lw = w;
            if (lw.empty()) lw = fw;
            for (int j : first[lw]) {
                if (i == j) continue;
                string merged = phrases[i] + phrases[j].substr(lw.size());
                ans.insert(merged);
            }
        }
        return vector<string>(ans.begin(), ans.end());
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


func beforeAndAfterPuzzles(phrases []string) []string {
    first := map[string][]int{}
    last := map[string][]int{}
    n := len(phrases)
    for i, ph := range phrases {
        ws := strings.Fields(ph)
        fw, lw := ws[0], ws[len(ws)-1]
        first[fw] = append(first[fw], i)
        last[lw] = append(last[lw], i)
    }
    ans := map[string]struct{}{}
    for i, ph := range phrases {
        ws := strings.Fields(ph)
        lw := ws[len(ws)-1]
        for _, j := range first[lw] {
            if i == j { continue }
            merged := ph + phrases[j][len(lw):]
            ans[merged] = struct{}{}
        }
    }
    res := make([]string, 0, len(ans))
    for k := range ans { res = append(res, k) }
    sort.Strings(res)
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    public List<String> beforeAndAfterPuzzles(String[] phrases) {
        Map<String, List<Integer>> first = new HashMap<>();
        int n = phrases.length;
        for (int i = 0; i < n; ++i) {
            String[] ws = phrases[i].split(" ");
            String fw = ws[0], lw = ws[ws.length-1];
            first.computeIfAbsent(fw, k -> new ArrayList<>()).add(i);
        }
        Set<String> ans = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            String[] ws = phrases[i].split(" ");
            String lw = ws[ws.length-1];
            for (int j : first.getOrDefault(lw, List.of())) {
                if (i == j) continue;
                String merged = phrases[i] + phrases[j].substring(lw.length());
                ans.add(merged);
            }
        }
        List<String> res = new ArrayList<>(ans);
        Collections.sort(res);
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    fun beforeAndAfterPuzzles(phrases: Array<String>): List<String> {
        val first = mutableMapOf<String, MutableList<Int>>()
        val n = phrases.size
        for (i in 0 until n) {
            val ws = phrases[i].split(" ")
            val fw = ws[0]
            first.getOrPut(fw) { mutableListOf() }.add(i)
        }
        val ans = mutableSetOf<String>()
        for (i in 0 until n) {
            val ws = phrases[i].split(" ")
            val lw = ws.last()
            for (j in first[lw] ?: emptyList()) {
                if (i == j) continue
                val merged = phrases[i] + phrases[j].substring(lw.length)
                ans.add(merged)
            }
        }
        return ans.sorted()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def beforeAndAfterPuzzles(self, phrases: list[str]) -> list[str]:
        from collections import defaultdict
        first = defaultdict(list)
        n = len(phrases)
        for i, ph in enumerate(phrases):
            ws = ph.split()
            first[ws[0]].append(i)
        ans = set()
        for i, ph in enumerate(phrases):
            ws = ph.split()
            lw = ws[-1]
            for j in first[lw]:
                if i == j:
                    continue
                merged = ph + phrases[j][len(lw):]
                ans.add(merged)
        return sorted(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


impl Solution {
    pub fn before_and_after_puzzles(phrases: Vec<String>) -> Vec<String> {
        use std::collections::{HashMap, HashSet};
        let n = phrases.len();
        let mut first: HashMap<&str, Vec<usize>> = HashMap::new();
        for (i, ph) in phrases.iter().enumerate() {
            let ws: Vec<&str> = ph.split(' ').collect();
            first.entry(ws[0]).or_default().push(i);
        }
        let mut ans = HashSet::new();
        for (i, ph) in phrases.iter().enumerate() {
            let ws: Vec<&str> = ph.split(' ').collect();
            let lw = ws[ws.len()-1];
            if let Some(js) = first.get(lw) {
                for &j in js {
                    if i == j { continue; }
                    let merged = format!("{}{}", ph, &phrases[j][lw.len()..]);
                    ans.insert(merged);
                }
            }
        }
        let mut res: Vec<String> = ans.into_iter().collect();
        res.sort();
        res
    }
}

Complexity

⏰ Time complexity: O(n^2 * L) — For each phrase, we may check all others, and merging takes up to L (phrase length).
🧺 Space complexity: O(nL) — For storing the mappings and results.

Problem#

Examples#

Solution#

Method 1 – Hash Map for First and Last Word Matching#

Intuition#

Approach#

Code#

Complexity#