2
$\begingroup$

Suppose that we are given a pattern $p$, which is a set of characters (order doesn't matter). We are also given a set of strings $A$. I want to find all of the strings in $A$ whose characters are all contained in $p$ (without taking the order of these characters into consideration), i.e., to find all $s \in A$ such that every character in $s$ is also in $p$.

The algorithm that I use is to loop every string in $A$ first, and, then, loop every character in each string, so the time complexity is $O(nm)$. My question is: is there any faster algorithm? Bit operation or matrix is ok.

Here is an example:

Pattern "abcdef"

Set A  {a, b, ac, ag, bde, cbd, daf, cg, abzdef, d} 

Desired results : a, b, ac, bde, cbd, daf, d

Filtered: ag, cg, abzdef (as g,z don't belong to the original string "abcdef")
$\endgroup$
  • 3
    $\begingroup$ What exactly is $n$ and $m$? $\endgroup$ – Mario Cervera Feb 23 '17 at 9:50
  • 1
    $\begingroup$ @Mario Cervera : just my wild guess, but I'm taking the O(nm) mentioned in the OP's question is alluding to n = size of A and m = max(length(s)) for all s in A. $\endgroup$ – YSharp Feb 26 '17 at 3:09
  • $\begingroup$ a pattern p, which is a set of characters (order doesn't matter) - so why call it pattern in the first place? $\endgroup$ – greybeard Apr 27 '17 at 10:19
4
$\begingroup$

You only need to read the strings in set $A$ and the characters in pattern $p$ once. You can store each character of $p$ in a hash table* for (expected) constant time lookup, and, then, perform a linear scan in $A$ to obtain the desired result. The running time of this solution is $O(n+m)$, where $n$ is the length (i.e., the total number of characters) of $A$ and $m$ is the length of $p$.

* A solution that is more space-efficient than the hash table (and guarantees constant time lookup) is to use a bit array $P$ to store pattern $p$. This array will be indexed by the ASCII values of all possible characters that you want to consider in your application; for instance, $P$ will have 26 index positions in the case of the English alphabet: one per distinct character. The $i$-th bit of $P$ will be set to $1$ if the $i$-th character appears in $p$, and to $0$ otherwise. Thus, you can scan $A$ in linear time and discard every string that contains at least one character $c$ such that $P[v_c]=0$, where $v_c$ is the ASCII value of $c$.

$\endgroup$
0
$\begingroup$

Mario Cervera's proposed structure is asymptotically the best you can do( O(n) ).
However there is a faster data structure for practical sets of Strings(such as the English words).
It is called a binary decision diagram.
Basically you create a binary tree 26 (size of alphabet) nodes deep. At the first level you have a node with value = 'a' and pointer to left and right subtree. In the left tree you store words containing 'a', in the right those that do not. next level is 'b' and so on... Then you traverse the tree in a special way to get all words that match the query. I have implemented this in Java, PM me if you want to see the source.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.