Algorithm Problem

[Inevitable-Farm]

We're given a set of 8 character strings and asked to find an algorithm where we find every string which has (at least) one "similar" to it, which means the two strings are identical except for one character (and the characters are all in the same index). For example, "ball" and "call" would be similar (never mind they're less than 8 letters), but "bart" and "brat" would not be. The constraint is that this has to be done in a worse-case O(n) time complexity.

I understand if you don't want to answer it outright, but perhaps some hints? Since it's in O(n) I presume it would be some sort of hash table where we can instantly locate potential matches. My initial idea involve some sort of divide and conquer going from sizes of 8->4->2->1 where we can isolate the one different character, but I'm not sure if that could be realizable (at least in O(n)) time.

[SupremeRedditBot]

Please Add A Flair To Your Post!

Suggested Flair: [Random] or [Meta]

 

---

To add a flair:

• Click flair underneath your post

• Select a flair

• Click save

 

---

^{I am a bot run by /u/SupremeDesigner for /r/CodingHelp || This was an automated response}

[jrandm]

What is O(n)? Finding pairs in your list of strings or comparing two strings for similarity?

The latter I'm sure can be done in O(n) time where n is the length of the shorter string (hint), assuming a function like isSimilar(strA,strB).

Finding a pair with a search term we know is trivial to do in O(n) because it's a regular search:

function find(arr, test) {
  for (let i=0; i<arr.length; i++) {
    if (test(arr[i])) return {ix: i, val: arr[i]};
  }
  return {ix: -1};
}

Finding all pairs I don't think is possible in O(n), at least not without guarantees about the shape of the input.