Iterate over the neighborhood of a string

Question

Input

A string S of length between 2 and 30. The only letters in the string will be a or b.

Output

All strings within Levenshtein distance 2 of S. You must output all the strings without duplicates but in any order you like.

Example

If S = aaa then the output would be (in any order):

aa
abab
ab
aabba
aaaa
abaa
bbaaa
aba
bbaa
babaa
bba
abaaa
abaab
baaa
baab
baaaa
baba
aabaa
ba
abba
aaba
aabb
abbaa
abb
aabab
aaaaa
aaaab
baaba
a
aaaba
aaabb
aaa
aab
ababa
aaab
bab
baa
baaab

Constraints

Your code must be fast enough that it would run to completion on TIO when S is of length 30. This is only to stop brute force solutions.

Answer 1

Haskell, 115 109 bytes

• -6 thanks to Unrelated String

import Data.List
f=nub.(=<<)g.g
g=(=<<)h.(zip.inits<*>tails)
h(x,y)=[x++b++c|b<-["a","b",""],c<-[y,drop 1 y]]

Try it online!

Explanation:

f :: String -> [String]
f=nub    -- delete duplicates
 .(=<<)g -- apply g to every result (get all words with distance <= 2)
 .g      -- apply g once to the input (get all words with distance <= 1)

g :: String -> [String]
g=(=<<)h               -- apply h to every split and flatten the resulting list
 .(zip.inits<*>tails)  -- split the string at every possible position

{- |
h takes a pair of Strings (x,y the input split at some point) and returns all
combinations of x, one of a, b or nothing, and y with the first letter present
or removed
("he","llo") -> ["heallo","healo","hebllo","heblo","hello","helo"]
drop 1 is basically the same as tail with the difference that drop 1 [] returns
[] instead of throwing an error
-}
h :: (String,String) -> [String]
h(x,y)=[x++b++c|b<-["a","b",""],c<-[y,drop 1 y]]

Answer 2

Charcoal, 66 bytes

⊞υθ≔⟦θ⟧ηＦη«≔⟦⟧ζＦＬιＦabＦ³⊞ζ⭆ι⎇⁻ξκν…⁺λνμＦab⊞ζ⁺ικＦζ¿¬№υκ«⊞υκ¿⁼ιθ⊞ηκ»»υ

Try it online! Link is to verbose version of code. Explanation:

⊞υθ

Push the input to the predefined empty list as the first result.

≔⟦θ⟧ηＦη«

Start a breadth-first search using the input.

≔⟦⟧ζ

Start collecting potential new results.

ＦＬιＦabＦ³

Loop over each index, each potential insert/edit, and each operation (0=delete, 1=edit, 2=insert).

⊞ζ⭆ι⎇⁻ξκν…⁺λνμ

Apply the specified operation to the appropriate index of the current string.

Ｆab⊞ζ⁺ικ

Also consider appending either of a and b to the current string.

Ｆζ¿¬№υκ«

For each string that has not been seen before, ...

⊞υκ

... push it to the result string, ...

¿⁼ιθ⊞ηκ

... and if we're modifying the original input then also push it to the search space.

»»υ

Finally print all the results.

Answer 3

Python 2, 113 bytes

Takes input as a singleton list containing the string.

s="{k[:i]+c+k[i+w:]for k in %sfor i in range(len(k)+1)for c in['','a','b']for w in(0,1)}"
print eval(s%s%input())

Try it online!

---

Python 3, 114 bytes

f=lambda s,d=2,i=0:d*s[i-1:]and{k[:i]+c+k[i+w:]for k in f(s,d-1)for c in['','a','b']for w in(0,1)}|f(s,d,i+1)or{s}

Try it online!

Commented:

f=lambda s,d=2,i=0:      # a recursive function with arguments:
                         #  - s, the input string
                         #  - d, the maximal Levensthein distance to s
                         #  - i, the index of the current operation
  d*s[i-1:]and ... or{s} # if d==0 or i>len(s) return a set containing s
                         # otherwise:
  {k[:i]+c+k[i+w:]       #  apply an operation
   for k in f(s,d-1)     #   on every string with maximal Levensthein distance d-1
   for c in['','a','b']  #   insert / replace with any of '', 'a', 'b'
   for w in(0,1)}        #   w==0: c=='': no operation, c!='': insertion
                         #   w==1: c=='': deletion,     c!='': replacement
  | f(s,d,i+1)           #  union this to the result of applying an operation at a larger index

Answer 4

JavaScript (ES6),  137 134 131  123 bytes

Expects a string with 0/1 instead of a/b. Returns an Object whose keys (and values) are the output strings.

f=(s,k=2,o={},p='')=>[...o[s]=s].map((c,i)=>k&&[p+(q=s.slice(i+1)),p+(C=c^1)+q,(p+=c)+0+q,p+1+q,C+s].map(s=>f(s,k-1,o)))&&o

Try it online!

Commented

This is a naive and rather lengthy implementation that just builds all the strings recursively.

f = (                         // f is a recursive function taking:
  s,                          //   s = input string
  k = 2,                      //   k = counter
  o = {},                     //   o = an object used to store the results
  p = ''                      //   p = current prefix
) =>                          //
  [...o[s] = s]               // save s into o and split s
  .map((c, i) =>              // for each character c at position i in s:
    k &&                      //   abort if k = 0
    [                         //   otherwise, build an array:
      p +                     //     remove c by concatenating the prefix p
      (q = s.slice(i + 1)),   //     with the suffix q
      p + (C = c ^ 1) + q,    //     modify c
      (p += c) + 0 + q,       //     insert '0' after c (and update p)
      p + 1 + q,              //     insert '1' after c
      C + s                   //     prepend the modified c at the beginning
                              //     (this case is not covered by the insertions)
    ]                         //   end of array
    .map(s => f(s, k - 1, o)) //   do a recursive call for each string in there
  )                           // end of map()
  && o                        // return o

Answer 5

Ruby 2.7, 115 109 bytes

Port of ovs's answer in Python!

f=->s,d=2,i=0{d>0&&s[i-1]?['',?a,?b].product(f[s,d-1],[0,1]).map{_2[...i]+_1+"#{_2[i+_3..]}"}|f[s,d,i+1]:[s]}

Try it online!

TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves 3 bytes, and we've begin-less ...i and end-less i+_3.. ranges, which saves 3 more bytes!

Answer 6

Haskell, 89 bytes

import Data.List
nub.(g=<<).g
g(h:t)=t:((:)<$>"ab"<*>[h:t,t])++map(h:)(g t)
g _=["a","b"]

Try it online!

The helper function g recursively generates all strings at Levenshtein distance 1.

Answer 7

K (ngn/k), 78 bytes

{?"ab"@?,/e'e"b"=x}
e:{?,/(~+x==#x;{y,x,z}.',/0 1,/:\:(0,'!1+#x)_\:x;x_/:!#x)}

Try it online!