CodeWars: Recover a secret string from random triplets Solution

It's easy to make thing more complicated

Approach: exhausive traversal with adjacent list

Build the map of letter and its adjacent letters

Traverse all the possible secret

The right secret is the one who mets the expected length

Implementation

1var recoverSecret = function (triplets) {
2 const vertices = new Set(triplets.reduce((acc, el) => acc.concat(el), []))
3 const secretLength = vertices.size
4 const verticeEdgesMap = new Map(
5 [...vertices].map(vertice => [vertice, new Set()])
6 )
7 const possibleSecrets = []
8
9 for (const [v1, v2, v3] of triplets) {
10 verticeEdgesMap.get(v1).add(v2)
11 verticeEdgesMap.get(v2).add(v3)
12
13 // after this, there would be only one head left
14 vertices.delete(v2)
15 vertices.delete(v3)
16 }
17
18 const recursion = (vertice, secret = "") => {
19 const edges = [...verticeEdgesMap.get(vertice)]
20
21 if (!edges.length) {
22 possibleSecrets.push(secret + vertice)
23 return
24 }
25
26 for (const adjacentVertice of edges) {
27 recursion(adjacentVertice, secret + vertice)
28 }
29 }
30
31 const head = [...vertices][0]
32 recursion(head)
33
34 return possibleSecrets.find(secret => secret.length === secretLength)
35}

Approach: keep picking heads

Pick a head and remove it from the triplet. Keep doing that till all triplets are empty

There would always be a head during each process

Implementation

1var recoverSecret = function (triplets) {
2 let res = ""
3
4 while (triplets.length) {
5 for (const [letter1] of triplets) {
6 const isHead = triplets.every(triplet => triplet.indexOf(letter1) <= 0)
7
8 if (!isHead) continue
9
10 res += letter1
11 triplets = triplets
12 .map(triplet => (triplet[0] === letter1 ? triplet.slice(1) : triplet))
13 .filter(triplet => triplet.length)
14
15 break
16 }
17 }
18
19 return res
20}

References

Original problem

Comments

Loading comments...

Tags

codewars

recursion

dfs

array

Next Post

LeetCode: Implement Queue using Stacks

Sep 30, 2022

Code speaks for itself

Previous Post

LeetCode: Same Tree

Sep 28, 2022

Recursion

HoningJS

Search Posts