CODEWITHSUNDEEP
javascripthashmap
TrickOrTreat
TrickOrTreat

Reputation: 911

How to get Similar Keys in Javascript Object to a given word in o(1) time complexity

Since I am working for over 15k properties in object so array system is not exactly what I am looking for. Any other solutions.

Is it possible to find similar keys with O(1) time complexity. For example:

const a = {
  warp1: 43,
  warp2: 87,
  warp.34: 19,
  warp_63: 82,
  warp_fundamental: 91,
  shop_41:9,
  warp.12:911,...
}

Let's say I want to extract all keys which begins with warp* and extract it in an array.

Solution which I am looking for is ['warp1','warp2', 'warp.34', 'warp_63','warp_fundamental', 'warp.12' ] Is it possible with javascript?

Upvotes: 0

Views: 45

Answers (1)

georg
georg

Reputation: 214969

As stated, it's impossible to do better than O(n^2), because you have to check each item, and, for each item, check each character of the search string (more precisely, O(n*m), i.e. number of items x length of the search).

However, if you're applying the search repeatedly to the same set of data, you can spend n^2 cycles first to build a trie and then perform subsequent searches in logarithmic time.

O(1) is only possible if you have a fixed set of search strings and precompute results for them all.

Upvotes: 2

Related Questions