Skip to content

1181. Before and After Puzzle ๐Ÿ”’

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. Note that only the last word of the first phrase and the first word of the second phrase are merged in this process.

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, after removing all duplicate phrases in the generated Before and After puzzles.

ย 

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"]

Example 4:

Input: phrases = ["ab ba","ba ab","ab ba"]

Output: ["ab ba ab","ba ab ba"]

ย 

Constraints:

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

Solutions

Solution 1: Hash Table + Sorting

First, we traverse the phrases list, storing the first and last words of each phrase in the array \(ps\), where \(ps[i][0]\) and \(ps[i][1]\) represent the first and last words of the \(i\)th phrase, respectively.

Next, we enumerate all \((i, j)\), where \(i, j \in [0, n)\) and \(i \neq j\). If \(ps[i][1] = ps[j][0]\), then we can concatenate the \(i\)th phrase and the \(j\)th phrase to get a new phrase \(phrases[i] + phrases[j][len(ps[j][0]):]\), and add the new phrase to the hash table \(s\).

Finally, we convert the hash table \(s\) into an array and sort it to get the answer.

The time complexity is \(O(n^2 \times m \times (\log n + \log m))\), and the space complexity is \(O(n^2 \times m)\). Here, \(n\) and \(m\) represent the length of the phrases array and the average length of each phrase, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
        ps = []
        for p in phrases:
            ws = p.split()
            ps.append((ws[0], ws[-1]))
        n = len(ps)
        ans = []
        for i in range(n):
            for j in range(n):
                if i != j and ps[i][1] == ps[j][0]:
                    ans.append(phrases[i] + phrases[j][len(ps[j][0]) :])
        return sorted(set(ans))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<String> beforeAndAfterPuzzles(String[] phrases) {
        int n = phrases.length;
        var ps = new String[n][];
        for (int i = 0; i < n; ++i) {
            var ws = phrases[i].split(" ");
            ps[i] = new String[] {ws[0], ws[ws.length - 1]};
        }
        Set<String> s = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j && ps[i][1].equals(ps[j][0])) {
                    s.add(phrases[i] + phrases[j].substring(ps[j][0].length()));
                }
            }
        }
        var ans = new ArrayList<>(s);
        Collections.sort(ans);
        return 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
27
class Solution {
public:
    vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
        int n = phrases.size();
        pair<string, string> ps[n];
        for (int i = 0; i < n; ++i) {
            int j = phrases[i].find(' ');
            if (j == string::npos) {
                ps[i] = {phrases[i], phrases[i]};
            } else {
                int k = phrases[i].rfind(' ');
                ps[i] = {phrases[i].substr(0, j), phrases[i].substr(k + 1)};
            }
        }
        unordered_set<string> s;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j && ps[i].second == ps[j].first) {
                    s.insert(phrases[i] + phrases[j].substr(ps[i].second.size()));
                }
            }
        }
        vector<string> ans(s.begin(), s.end());
        sort(ans.begin(), ans.end());
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func beforeAndAfterPuzzles(phrases []string) []string {
    n := len(phrases)
    ps := make([][2]string, n)
    for i, p := range phrases {
        ws := strings.Split(p, " ")
        ps[i] = [2]string{ws[0], ws[len(ws)-1]}
    }
    s := map[string]bool{}
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j && ps[i][1] == ps[j][0] {
                s[phrases[i]+phrases[j][len(ps[j][0]):]] = true
            }
        }
    }
    ans := make([]string, 0, len(s))
    for k := range s {
        ans = append(ans, k)
    }
    sort.Strings(ans)
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function beforeAndAfterPuzzles(phrases: string[]): string[] {
    const ps: string[][] = [];
    for (const p of phrases) {
        const ws = p.split(' ');
        ps.push([ws[0], ws[ws.length - 1]]);
    }
    const n = ps.length;
    const s: Set<string> = new Set();
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            if (i !== j && ps[i][1] === ps[j][0]) {
                s.add(`${phrases[i]}${phrases[j].substring(ps[j][0].length)}`);
            }
        }
    }
    return [...s].sort();
}

Comments