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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var recoverSecret = function (triplets) {2  const vertices = new Set(triplets.reduce((acc, el) => acc.concat(el), []))3  const secretLength = vertices.size4  const verticeEdgesMap = new Map(5    [...vertices].map(vertice => [vertice, new Set()])6  )7  const possibleSecrets = []8
13    // after this, there would be only one head left14    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      return24    }25
26    for (const adjacentVertice of edges) {27      recursion(adjacentVertice, secret + vertice)28    }29  }30
34  return possibleSecrets.find(secret => secret.length === secretLength)35}```

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
10      res += letter111      triplets = triplets12        .map(triplet => (triplet[0] === letter1 ? triplet.slice(1) : triplet))13        .filter(triplet => triplet.length)14
15      break16    }17  }18
19  return res20}```

Original problem

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

Search Posts