A Fun Little Task
February 28, 2017
Today’s exercise is a fun little task:
Given two strings a and b, with a no longer than b, determine if there is any permutation of a that appears in b. For instance, a permutation of string xyz appears starting at the fourth character (counting from zero) of string afdgzyxksldfm.
Your task is to write a program to determine is any permutation of a string is a substring of another string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Isn’t this the same as https://programmingpraxis.com/2014/02/21/anagrams-within-words/ – I was thinking “Hmm, an incrementally modified multiset would do nicely here” and then I remembered https://programmingpraxis.com/2014/02/21/anagrams-within-words/#comment-19023 (possibly my first contribution here).
Shhh. You found my secret. Don’t tell anybody.
Indeed, we did this exercise before. Here another Python version.
I don’t see this python solution in either exercise.
Use itertools.groupby() on the second string to collect runs of characters that are in the first string. Then, use collections.Counter as a multiset to compare a multiset of each run with a multiset of the first string. Linear complexity, I think.
@Mike: your method returns False for (a, b) = (“xxx”, “xxxx”). You still have to make sure that your runs have the same length as a.
A solution in Racket.
A Haskell version.
sub present{
@c = split(“”,$b);
print “$c[0]$c[1]$c[2]\n”;
$len = length($b);
for($i = 0;$i<=$len;$i++)
{
$x=$c[$i].$c[$i+1].$c[$i+2];
if($a eq $x)
{
print "YES\n";
}
}
}
Another Python version.
from itertools import product
def check(str_1, str_2):
s_1 = ''.join(sorted(str_1))
pos = [i for i,x in enumerate(str_2) if x == s_1[0]]
return any(j-k >= 0 and s_1 == ''.join(sorted(str_2[j-k:j+len(str_1)-k]))
for j, k in product(pos, range(len(str_1))))