How can I replace two strings in a way that one does not end up replacing the other?

Question

Let's say that I have the following code:

String word1 = "bar";
String word2 = "foo";
String story = "Once upon a time, there was a foo and a bar."
story = story.replace("foo", word1);
story = story.replace("bar", word2);

After this code runs, the value of story will be "Once upon a time, there was a foo and a foo."

A similar issue occurs if I replaced them in the opposite order:

String word1 = "bar";
String word2 = "foo";
String story = "Once upon a time, there was a foo and a bar."
story = story.replace("bar", word2);
story = story.replace("foo", word1);

The value of story will be "Once upon a time, there was a bar and a bar."

My goal is to turn story into "Once upon a time, there was a bar and a foo." How could I accomplish that?

Answer 1

Use the replaceEach() method from Apache Commons StringUtils:

StringUtils.replaceEach(story, new String[]{"foo", "bar"}, new String[]{"bar", "foo"})

Answer 2

You use an intermediate value (which is not yet present in the sentence).

story = story.replace("foo", "lala");
story = story.replace("bar", "foo");
story = story.replace("lala", "bar");

As a response to criticism: if you use a large enough uncommon string like zq515sqdqs5d5sq1dqs4d1q5dqqé"&é5d4sqjshsjddjhodfqsqc, nvùq^µù;d&€sdq: d: ;)àçàçlala and use that, it is unlikely to the point where I won't even debate it that a user will ever enter this. The only way to know whether a user will is by knowing the source code and at that point you're with a whole other level of worries.

Yes, maybe there are fancy regex ways. I prefer something readable that I know will not break out on me either.

Also reiterating the excellent advise given by @David Conrad in the comments:

Don't use some string cleverly (stupidly) chosen to be unlikely. Use characters from the Unicode Private Use Area, U+E000..U+F8FF. Remove any such characters first, since they shouldn't legitimately be in the input (they only have application-specific meaning within some application), then use them as placeholders when replacing.

Answer 3

You can try something like this, using Matcher#appendReplacement and Matcher#appendTail:

String word1 = "bar";
String word2 = "foo";
String story = "Once upon a time, there was a foo and a bar.";

Pattern p = Pattern.compile("foo|bar");
Matcher m = p.matcher(story);
StringBuffer sb = new StringBuffer();
while (m.find()) {
    /* do the swap... */
    switch (m.group()) {
    case "foo":
        m.appendReplacement(sb, word1);
        break;
    case "bar":
        m.appendReplacement(sb, word2);
        break;
    default:
        /* error */
        break;
    }
}
m.appendTail(sb);

System.out.println(sb.toString());

Once upon a time, there was a bar and a foo.

Answer 4

This is not an easy problem. And the more search-replacement parameters you have, the trickier it gets. You have several options, scattered on the palette of ugly-elegant, efficient-wasteful:

• Use StringUtils.replaceEach from Apache Commons as @AlanHay recommended. This is a good option if you're free to add new dependencies in your project. You might get lucky: the dependency might be included already in your project

• Use a temporary placeholder as @Jeroen suggested, and perform the replacement in 2 steps:

  1. Replace all search patterns with a unique tag that doesn't exist in the original text
  2. Replace the placeholders with the real target replacement

  This is not a great approach, for several reasons: it needs to ensure that the tags used in the first step are really unique; it performs more string replacement operations than really necessary

• Build a regex from all the patterns and use the method with Matcher and StringBuffer as suggested by @arshajii. This is not terrible, but not that great either, as building the regex is kind of hackish, and it involves StringBuffer which went out of fashion a while ago in favor of StringBuilder.

• Use a recursive solution proposed by @mjolka, by splitting the string at the matched patterns, and recursing on the remaining segments. This is a fine solution, compact and quite elegant. Its weakness is the potentially many substring and concatenation operations, and the stack size limits that apply to all recursive solutions

• Split the text to words and use Java 8 streams to perform the replacements elegantly as @msandiford suggested, but of course that only works if you are ok with splitting at word boundaries, which makes it not suitable as a general solution

Here's my version, based on ideas borrowed from Apache's implementation. It's neither simple nor elegant, but it works, and should be relatively efficient, without unnecessary steps. In a nutshell, it works like this: repeatedly find the next matching search pattern in the text, and use a StringBuilder to accumulate the unmatched segments and the replacements.

public static String replaceEach(String text, String[] searchList, String[] replacementList) {
    // TODO: throw new IllegalArgumentException() if any param doesn't make sense
    //validateParams(text, searchList, replacementList);

    SearchTracker tracker = new SearchTracker(text, searchList, replacementList);
    if (!tracker.hasNextMatch(0)) {
        return text;
    }

    StringBuilder buf = new StringBuilder(text.length() * 2);
    int start = 0;

    do {
        SearchTracker.MatchInfo matchInfo = tracker.matchInfo;
        int textIndex = matchInfo.textIndex;
        String pattern = matchInfo.pattern;
        String replacement = matchInfo.replacement;

        buf.append(text.substring(start, textIndex));
        buf.append(replacement);

        start = textIndex + pattern.length();
    } while (tracker.hasNextMatch(start));

    return buf.append(text.substring(start)).toString();
}

private static class SearchTracker {

    private final String text;

    private final Map<String, String> patternToReplacement = new HashMap<>();
    private final Set<String> pendingPatterns = new HashSet<>();

    private MatchInfo matchInfo = null;

    private static class MatchInfo {
        private final String pattern;
        private final String replacement;
        private final int textIndex;

        private MatchInfo(String pattern, String replacement, int textIndex) {
            this.pattern = pattern;
            this.replacement = replacement;
            this.textIndex = textIndex;
        }
    }

    private SearchTracker(String text, String[] searchList, String[] replacementList) {
        this.text = text;
        for (int i = 0; i < searchList.length; ++i) {
            String pattern = searchList[i];
            patternToReplacement.put(pattern, replacementList[i]);
            pendingPatterns.add(pattern);
        }
    }

    boolean hasNextMatch(int start) {
        int textIndex = -1;
        String nextPattern = null;

        for (String pattern : new ArrayList<>(pendingPatterns)) {
            int matchIndex = text.indexOf(pattern, start);
            if (matchIndex == -1) {
                pendingPatterns.remove(pattern);
            } else {
                if (textIndex == -1 || matchIndex < textIndex) {
                    textIndex = matchIndex;
                    nextPattern = pattern;
                }
            }
        }

        if (nextPattern != null) {
            matchInfo = new MatchInfo(nextPattern, patternToReplacement.get(nextPattern), textIndex);
            return true;
        }
        return false;
    }
}

Unit tests:

@Test
public void testSingleExact() {
    assertEquals("bar", StringUtils.replaceEach("foo", new String[]{"foo"}, new String[]{"bar"}));
}

@Test
public void testReplaceTwice() {
    assertEquals("barbar", StringUtils.replaceEach("foofoo", new String[]{"foo"}, new String[]{"bar"}));
}

@Test
public void testReplaceTwoPatterns() {
    assertEquals("barbaz", StringUtils.replaceEach("foobar",
            new String[]{"foo", "bar"},
            new String[]{"bar", "baz"}));
}

@Test
public void testReplaceNone() {
    assertEquals("foofoo", StringUtils.replaceEach("foofoo", new String[]{"x"}, new String[]{"bar"}));
}

@Test
public void testStory() {
    assertEquals("Once upon a foo, there was a bar and a baz, and another bar and a cat.",
            StringUtils.replaceEach("Once upon a baz, there was a foo and a bar, and another foo and a cat.",
                    new String[]{"foo", "bar", "baz"},
                    new String[]{"bar", "baz", "foo"})
    );
}

Answer 5

Search for the first word to be replaced. If it's in the string, recurse on the the part of the string before the occurrence, and on the part of the string after the occurrence.

Otherwise, continue with the next word to be replaced.

A naive implementation might look like this

public static String replaceAll(String input, String[] search, String[] replace) {
  return replaceAll(input, search, replace, 0);
}

private static String replaceAll(String input, String[] search, String[] replace, int i) {
  if (i == search.length) {
    return input;
  }
  int j = input.indexOf(search[i]);
  if (j == -1) {
    return replaceAll(input, search, replace, i + 1);
  }
  return replaceAll(input.substring(0, j), search, replace, i + 1) +
         replace[i] +
         replaceAll(input.substring(j + search[i].length()), search, replace, i);
}

Sample usage:

String input = "Once upon a baz, there was a foo and a bar.";
String[] search = new String[] { "foo", "bar", "baz" };
String[] replace = new String[] { "bar", "baz", "foo" };
System.out.println(replaceAll(input, search, replace));

Output:

Once upon a foo, there was a bar and a baz.

---

A less-naive version:

public static String replaceAll(String input, String[] search, String[] replace) {
  StringBuilder sb = new StringBuilder();
  replaceAll(sb, input, 0, input.length(), search, replace, 0);
  return sb.toString();
}

private static void replaceAll(StringBuilder sb, String input, int start, int end, String[] search, String[] replace, int i) {
  while (i < search.length && start < end) {
    int j = indexOf(input, search[i], start, end);
    if (j == -1) {
      i++;
    } else {
      replaceAll(sb, input, start, j, search, replace, i + 1);
      sb.append(replace[i]);
      start = j + search[i].length();
    }
  }
  sb.append(input, start, end);
}

Unfortunately, Java's String has no indexOf(String str, int fromIndex, int toIndex) method. I've omitted the implementation of indexOf here as I'm not certain it's correct, but it can be found on ideone, along with some rough timings of various solutions posted here.

Answer 6

One-liner in Java 8:

    story = Pattern
        .compile(String.format("(?<=%1$s)|(?=%1$s)", "foo|bar"))
        .splitAsStream(story)
        .map(w -> ImmutableMap.of("bar", "foo", "foo", "bar").getOrDefault(w, w))
        .collect(Collectors.joining());

• Lookaround regular expressions (?<=, ?=): http://www.regular-expressions.info/lookaround.html
• If the words can contain special regex characters, use Pattern.quote to escape them.
• I use guava ImmutableMap for conciseness, but obviously any other Map will do the job as well.

Answer 7

Here is a Java 8 streams possibility that might be interesting for some:

String word1 = "bar";
String word2 = "foo";

String story = "Once upon a time, there was a foo and a bar.";

// Map is from untranslated word to translated word
Map<String, String> wordMap = new HashMap<>();
wordMap.put(word1, word2);
wordMap.put(word2, word1);

// Split on word boundaries so we retain whitespace.
String translated = Arrays.stream(story.split("\\b"))
    .map(w -> wordMap.getOrDefault(w,  w))
    .collect(Collectors.joining());

System.out.println(translated);

---

Here is an approximation of the same algorithm in Java 7:

String word1 = "bar";
String word2 = "foo";
String story = "Once upon a time, there was a foo and a bar.";

// Map is from untranslated word to translated word
Map<String, String> wordMap = new HashMap<>();
wordMap.put(word1, word2);
wordMap.put(word2, word1);

// Split on word boundaries so we retain whitespace.
StringBuilder translated = new StringBuilder();
for (String w : story.split("\\b"))
{
  String tw = wordMap.get(w);
  translated.append(tw != null ? tw : w);
}

System.out.println(translated);

Answer 8

​If you want to replace words in a sentence which are separated by white space as shown in your example you can use this simple algorithm.

1. Split story on white space
2. Replace each elements, if foo replace it to bar and vice varsa
3. Join the array back into one string

​If Splitting on space is not acceptable one can follow this alternate algorithm. ​You need to use the longer string first. If the stringes are foo and fool, you need to use fool first and then foo.

1. Split on the word foo
2. Replace bar with foo each element of the array
3. Join that array back adding bar after each element except the last

Answer 9

Here's a less complicated answer using Map.

private static String replaceEach(String str,Map<String, String> map) {

         Object[] keys = map.keySet().toArray();
         for(int x = 0 ; x < keys.length ; x ++ ) {
             str = str.replace((String) keys[x],"%"+x);
         }

         for(int x = 0 ; x < keys.length ; x ++) {
             str = str.replace("%"+x,map.get(keys[x]));
         }
         return str;
     }

And method is called

Map<String, String> replaceStr = new HashMap<>();
replaceStr.put("Raffy","awesome");
replaceStr.put("awesome","Raffy");
String replaced = replaceEach("Raffy is awesome, awesome awesome is Raffy Raffy", replaceStr);

Output is: awesome is Raffy, Raffy Raffy is awesome awesome

Answer 10

If you want to be able to handle multiple occurrences of the search strings to be replaced, you can do that easily by splitting the string on each search term, then replacing it. Here is an example:

String regex = word1 + "|" + word2;
String[] values = Pattern.compile(regex).split(story);

String result;
foreach subStr in values
{
   subStr = subStr.replace(word1, word2);
   subStr = subStr.replace(word2, word1);
   result += subStr;
}

Answer 11

You can accomplish your goal with the following code block:

String word1 = "bar";
String word2 = "foo";
String story = "Once upon a time, in a foo, there was a foo and a bar.";
story = String.format(story.replace(word1, "%1$s").replace(word2, "%2$s"),
    word2, word1);

It replaces the words regardless of the order. You can extend this principle into an utility method, like:

private static String replace(String source, String[] targets, String[] replacements) throws IllegalArgumentException {
    if (source == null) {
        throw new IllegalArgumentException("The parameter \"source\" cannot be null.");
    }

    if (targets == null || replacements == null) {
        throw new IllegalArgumentException("Neither parameters \"targets\" or \"replacements\" can be null.");
    }

    if (targets.length == 0 || targets.length != replacements.length) {
        throw new IllegalArgumentException("The parameters \"targets\" and \"replacements\" must have at least one item and have the same length.");
    }

    String outputMask = source;
    for (int i = 0; i < targets.length; i++) {
        outputMask = outputMask.replace(targets[i], "%" + (i + 1) + "$s");
    }

    return String.format(outputMask, (Object[])replacements);
}

Which would be consumed as:

String story = "Once upon a time, in a foo, there was a foo and a bar.";
story = replace(story, new String[] { "bar", "foo" },
    new String[] { "foo", "bar" }));

Answer 12

This works and is simple:

public String replaceBoth(String text, String token1, String token2) {            
    return text.replace(token1, "\ufdd0").replace(token2, token1).replace("\ufdd0", token2);
    }

You use it like this:

replaceBoth("Once upon a time, there was a foo and a bar.", "foo", "bar");

Note: this counts on Strings not containing character \ufdd0, which is a character permanently reserved for internal use by Unicode (See http://www.unicode.org/faq/private_use.html):

I don't think it's necessary, but If you want to be absolutely safe you can use:

public String replaceBoth(String text, String token1, String token2) {
    if (text.contains("\ufdd0") || token1.contains("\ufdd0") || token2.contains("\ufdd0")) throw new IllegalArgumentException("Invalid character.");
    return text.replace(token1, "\ufdd0").replace(token2, token1).replace("\ufdd0", token2);
    }

Answer 13

Swapping Only One Occurrence

If there is only one occurrence of each of the swapable strings in the input, you can do the following:

Before proceeding to any replace, get the indices of the occurrences of the words. After that we only replace the word found at these indexes, and not all occurrences. This solution uses StringBuilder and does not produce intermediate Strings like String.replace().

One thing to note: if the swapable words have different lengths, after the first replace the second index might change (if the 1st word occurs before the 2nd) exactly with the difference of the 2 lengths. So aligning the second index will ensure this works even if we're swapping words with different lengths.

public static String swap(String src, String s1, String s2) {
    StringBuilder sb = new StringBuilder(src);
    int i1 = src.indexOf(s1);
    int i2 = src.indexOf(s2);

    sb.replace(i1, i1 + s1.length(), s2); // Replace s1 with s2
    // If s1 was before s2, idx2 might have changed after the replace
    if (i1 < i2)
        i2 += s2.length() - s1.length();
    sb.replace(i2, i2 + s2.length(), s1); // Replace s2 with s1

    return sb.toString();
}

Swapping Arbitrary Number of Occurrences

Analogous to the previous case we will first collect the indexes (occurrences) of the words, but in this case it will a list of integers for each word, not just one int. For this we will use the following utility method:

public static List<Integer> occurrences(String src, String s) {
    List<Integer> list = new ArrayList<>();
    for (int idx = 0;;)
        if ((idx = src.indexOf(s, idx)) >= 0) {
            list.add(idx);
            idx += s.length();
        } else
            return list;
}

And using this we will replace the words with the other one by decreasing index (which might require to alternate between the 2 swapable words) so that we won't even have to correct the indices after a replace:

public static String swapAll(String src, String s1, String s2) {
    List<Integer> l1 = occurrences(src, s1), l2 = occurrences(src, s2);

    StringBuilder sb = new StringBuilder(src);

    // Replace occurrences by decreasing index, alternating between s1 and s2
    for (int i1 = l1.size() - 1, i2 = l2.size() - 1; i1 >= 0 || i2 >= 0;) {
        int idx1 = i1 < 0 ? -1 : l1.get(i1);
        int idx2 = i2 < 0 ? -1 : l2.get(i2);
        if (idx1 > idx2) { // Replace s1 with s2
            sb.replace(idx1, idx1 + s1.length(), s2);
            i1--;
        } else { // Replace s2 with s1
            sb.replace(idx2, idx2 + s2.length(), s1);
            i2--;
        }
    }

    return sb.toString();
}

Answer 14

It's easy to write a method to do this using String.regionMatches:

public static String simultaneousReplace(String subject, String... pairs) {
    if (pairs.length % 2 != 0) throw new IllegalArgumentException(
        "Strings to find and replace are not paired.");
    StringBuilder sb = new StringBuilder();
    outer:
    for (int i = 0; i < subject.length(); i++) {
        for (int j = 0; j < pairs.length; j += 2) {
            String find = pairs[j];
            if (subject.regionMatches(i, find, 0, find.length())) {
                sb.append(pairs[j + 1]);
                i += find.length() - 1;
                continue outer;
            }
        }
        sb.append(subject.charAt(i));
    }
    return sb.toString();
}

Testing:

String s = "There are three cats and two dogs.";
s = simultaneousReplace(s,
    "cats", "dogs",
    "dogs", "budgies");
System.out.println(s);

Output:

There are three dogs and two budgies.

It is not immediately obvious, but a function like this can still be dependent on the order in which the replacements are specified. Consider:

String truth = "Java is to JavaScript";
truth += " as " + simultaneousReplace(truth,
    "JavaScript", "Hamster",
    "Java", "Ham");
System.out.println(truth);

Output:

Java is to JavaScript as Ham is to Hamster

But reverse the replacements:

truth += " as " + simultaneousReplace(truth,
    "Java", "Ham",
    "JavaScript", "Hamster");

Output:

Java is to JavaScript as Ham is to HamScript

Oops! :)

Therefore it is sometimes useful to make sure to look for the longest match (as PHP's strtr function does, for example). This version of the method will do that:

public static String simultaneousReplace(String subject, String... pairs) {
    if (pairs.length % 2 != 0) throw new IllegalArgumentException(
        "Strings to find and replace are not paired.");
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < subject.length(); i++) {
        int longestMatchIndex = -1;
        int longestMatchLength = -1;
        for (int j = 0; j < pairs.length; j += 2) {
            String find = pairs[j];
            if (subject.regionMatches(i, find, 0, find.length())) {
                if (find.length() > longestMatchLength) {
                    longestMatchIndex = j;
                    longestMatchLength = find.length();
                }
            }
        }
        if (longestMatchIndex >= 0) {
            sb.append(pairs[longestMatchIndex + 1]);
            i += longestMatchLength - 1;
        } else {
            sb.append(subject.charAt(i));
        }
    }
    return sb.toString();
}

Note that the above methods are case-sensitive. If you need a case-insensitive version it is easy to modify the above because String.regionMatches can take an ignoreCase parameter.