Substitute substring within a string bidrectionally

Question

Given a string M that contains term A and B, I would like to substitute every A for B and every B for A to for M'. Naively one would try replacing A by B and then subsequently B by A but in that case the M' contains only of A. I can think of replacing the terms and record their position so that the terms do not get replaced again. This works when we only have A and B to replace. But if we need to substitute more than 2 terms and they are of different length then it gets tricky.

So I thought about doing this:

We are given M as input string and R = [(x1, y1), (x2, y2), ... (xn, yn)] as terms to replace, where we replace xi for yi for all i.
With M, Initiate L = [(M, false)] to be a list of (string * boolean) tuple where false means that this string has not been replaced.
Search for occurence of xi in each member L(i) of L with second term false. Partition L(i) into [(pre, false), (xi, false), (post, false)], and map to [(pre, false), (yi, true), (post, false)] where pre and post are string before and after xi. Flatten L.
Repeat the above until R is exhausted.
Concatenate the first element of each tuple of L to from M'.

Is there a more efficient way of doing this?

You'd better try out by your own. Regex are powerfull but and you'll need o know how its works by your own to know when to use it. — Anthony Raymond, Jul 19 '15 at 21:42
I think my question is just a more narrow case of http://stackoverflow.com/questions/15604140/replace-multiple-strings-with-multiple-other-strings — xiamx, Jul 20 '15 at 00:48

Amit · Answer 1 · 2015-07-20T06:18:08.400

0

Here's a regex solution:

var M = 'foobazbar123foo match';

var pairs = {
  'foo': 'bar',
  'bar': 'foo',
  'baz': 'quz',
  'no': 'match'
};

var re = new RegExp(Object.keys(pairs).join('|'),'g');

alert(M.replace(re, function(m) { return pairs[m]; }));

Note: This is a demonstration / POC. A real implementation would have to handle proper escaping of the lookup strings.

edited Jul 20 '15 at 06:18

answered Jul 19 '15 at 21:44

Amit

45,440
9
78
110

I guess you miss understood the question. let M be "foobar" and A = "foo" B="bar". The result should be "barfoo". A simple replace is easy but this question asks for bidirectional replace. – xiamx Jul 19 '15 at 21:46
@xiamx better now? (It was bidi in the first demo as well) – Amit Jul 19 '15 at 21:48
Ah sorry it's my bad, I didn't read it well. Nice to know regex can do that. How do I extend this to multiple pairs of a and b's? – xiamx Jul 19 '15 at 21:55
1

It's not that hard, but I can't do it right now. I promise an answer tomorrow! – Amit Jul 19 '15 at 21:56

user1952500 · Answer 2 · 2015-07-20T07:25:54.173

Another approach is to replace strings by intermediate temporary strings (symbols) and then replace symbols by their original counterparts. So the transformation 'foo' => 'bar' can be transformed in two steps as, say, 'foo' => '___1' => 'bar'. The other transformation 'bar' ==> 'foo' will then become 'bar' ==> '___2' ==> 'foo'. This will prevent the mixup you describe.

Sample python code for the same example as the other answer follows:

import re
def substr(string):
   repdict = {"foo":"bar", "bar":"foo", "baz":"quz", "no":"match"}
   tmpdict = dict()
   count = 0
   for left, right in repdict.items():
      tmpleft = "___" + count.__str__()
      tmpdict[tmpleft] = right
      count = count + 1
      tmpright = "___" + count.__str__()
      tmpdict[tmpright] = left
      count = count + 1
      string = re.sub(left, tmpleft, string)
      string = re.sub(right, tmpright, string)
   for tmpleft, tmpright in tmpdict.items():
      string = re.sub(tmpleft, tmpright, string)
   print string

>>> substr("foobazbar123foo match")
barquzfoo123bar no

Substitute substring within a string bidrectionally

2 Answers2