Efficient way to replace chars in a string (java)?

Question

I'm writing a small JAVA program which:

takes a text as a String
takes 2 arrays of chars

What im trying to do will sound like "find and replace" but it is not the same so i thought its important to clear it.

Anyway I want to take this text, find if any char from the first array match a char in the text and if so, replace it with the matching char (according to index) from the second char array.

I'll explain with an example: lets say my text (String) is: "java is awesome!"; i have 2 arrays (char[]): "absm" and "!@*$".

The wished result is to change 'a' to '!' , 'b' to '@' and so on.. meaning the resulted text will be:

"java is awesome!" changed to -> "j@v@ i* @w*o$e!"

What is the most efficient way of doing this and why? I thought about looping the text, but then i found it not so efficient.

(StringBuilder/String class can be used)

Let us see what you have done so far

Beau Grantham
– Beau Grantham

2011-11-23 20:29:48 +00:00
Commented Nov 23, 2011 at 20:29 — Beau Grantham
– Beau Grantham, Commented Nov 23, 2011 at 20:29
If you want to have a replaced by !, how do get j@v@?

jeha
– jeha

2011-11-23 20:40:35 +00:00
Commented Nov 23, 2011 at 20:40 — jeha
– jeha, Commented Nov 23, 2011 at 20:40

aeoliant · Accepted Answer · 2011-11-23 20:42:35Z

4

StringBuilder sb = new StringBuilder(text);
    for(int i = 0; i<text.length(); i ++)
    {
        for (int j = 0; j < firstCharArray.length;j++)
        {
            if (sb.charAt(i) == firstCharArray[j])
            {
                sb.setCharAt(i, secondCharArray[j]);
                break;
            }

        }
    }

This way is efficient because it uses a StringBuilder to change the characters in place (if you used Strings you would have to create new ones each time because they are immutable.) Also it minimizes the amount of passes you have to do (1 pass through the text string and n passes through the first array where n = text.length())

answered Nov 23, 2011 at 20:42

aeoliant

3872 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Popokoko Over a year ago

Okay this is sort of what I was trying to do. I just tested your code, it worked perfectly! Thanks a lot. **A little question: ** this code is looping each char in the text and for every char it loops the first char array. meanning for the second char in the text we'll loop again the first char, im guessing there's no other way? :S

aeoliant Over a year ago

What if the second char in the text was the first char in the array?

Popokoko Over a year ago

I didn't quite understand what u meant? Maybe it's my fault i just read what i wrote to u last post, anyway ill clear what i meant... lets say i have a string with 4 length and two arrays while the two of them are same size lets say 2 length. at first we iterate the 1/4 char of text and we go through the whole array (x2) then we iterate the 2/4 char.. and so on we keep checking same options again and again so i wasnt sure how efficient it is..

jeha · Accepted Answer · 2011-11-23 20:45:14Z

3

I guess you are looking for StringUtils.replaceEach, at least as a reference.

edited Nov 23, 2011 at 20:45

answered Nov 23, 2011 at 20:34

jeha

10.8k5 gold badges55 silver badges72 bronze badges

2 Comments

BenCole Over a year ago

Seems to be exactly what OP is looking for.

Ed Staub Over a year ago

The OP asked for efficient. This takes arrays of variable-length strings, not characters, which makes it somewhat inefficient.

dann.dev · Accepted Answer · 2011-11-23 20:34:03Z

1

How efficient do you need it to be? Are you doing this for hundreds, thousands, millions of words???

I don't know if it's the most efficent, but you could use the string indexOf() method on each of your possible tokens, it will tell you if it's there, and then you can replace that index at the same time with the corresponding char from the other array.

Codewise, something like (this is half pseudo code by the way):

for(each of first array) {
    int temp = YourString.indexOf(current array field);
    if (temp >=0) {
        replace with other array
    }
}

answered Nov 23, 2011 at 20:34

dann.dev

2,5033 gold badges21 silver badges32 bronze badges

Comments

Mechkov · Accepted Answer · 2011-11-23 20:36:46Z

1

Put the 2 arrays you have in a Map

Map<Character, Character> //or Map of Strings

where the key is "a", "b" etc... and the value is the character you want to substitute with - "@" etc....

Then simply replace the keys in your String with the values.

answered Nov 23, 2011 at 20:36

Mechkov

4,3241 gold badge20 silver badges25 bronze badges

2 Comments

Popokoko Over a year ago

Thanks but this example is too advanced since I'm not supposed to use this object.

Mechkov Over a year ago

No problem. Just something to think about later on.

Thanh Nguyen Van · Accepted Answer · 2016-09-13 09:32:40Z

1

For small stuff like this, an indexOf() search is likely to be faster than a map, while "avoiding" the inner loop of the accepted answer. Of course, the loop is still there, inside String.indexOf(), but it's likely to be optimized to a fare-thee-well by the JIT-compiler, because it's so heavily used.

static String replaceChars(String source, String from, String to)
{
    StringBuilder dest = new StringBuilder(source);
    for ( int i = 0; i < source.length(); i++ )
    {
        int foundAt = from.indexOf(source.charAt(i));
        if ( foundAt >= 0 )
            dest.setCharAt(i,to.charAt(foundAt));
    }
    return dest.toString();
}

Update: The Oracle/Sun JIT uses SIMD on at least some processors for indexOf(), making it even faster than one would guess.

edited Sep 13, 2016 at 9:32

Thanh Nguyen Van

1,9931 gold badge18 silver badges18 bronze badges

answered Nov 23, 2011 at 21:15

Ed Staub

15.8k3 gold badges63 silver badges91 bronze badges

1 Comment

Thanh Nguyen Van Over a year ago

I tried accepted solution and your solution. And I found that your solution run much faster (2 time). Thank you very much!

yair · Accepted Answer · 2011-11-23 20:40:33Z

0

Since the only way to know if a character should be replaced is to check it, you (or any util method) have to loop through the whole text, character after the other. You can never achieve better complexity than O(n) (n be the number of characters in the text).

edited Nov 23, 2011 at 20:40

answered Nov 23, 2011 at 20:34

yair

9,2954 gold badges36 silver badges53 bronze badges

Comments

fabiolimace · Accepted Answer · 2020-07-25 18:37:15Z

This utility class that replaces a char or a group of chars of a String. It is equivalent to bash tr and perl tr///, aka, transliterate.

/**
 * Utility class that replaces chars of a String, aka, transliterate.
 * 
 * It's equivalent to bash 'tr' and perl 'tr///'.
 *
 */
public class ReplaceChars {

    public static String replace(String string, String from, String to) {
        return new String(replace(string.toCharArray(), from.toCharArray(), to.toCharArray()));
    }

    public static char[] replace(char[] chars, char[] from, char[] to) {

        char[] output = chars.clone();
        for (int i = 0; i < output.length; i++) {
            for (int j = 0; j < from.length; j++) {
                if (output[i] == from[j]) {
                    output[i] = to[j];
                    break;
                }
            }
        }
        return output;
    }

    /**
     * For tests!
     */
    public static void main(String[] args) {

        // Example from: https://en.wikipedia.org/wiki/Caesar_cipher
        String string = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG";
        String from = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        String to = "XYZABCDEFGHIJKLMNOPQRSTUVW";

        System.out.println();
        System.out.println("Cesar cypher: " + string);
        System.out.println("Result:       " + ReplaceChars.replace(string, from, to));
    }
}

This is the output:

Cesar cypher: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
Result:       QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Collectives™ on Stack Overflow

Efficient way to replace chars in a string (java)?

7 Answers 7

3 Comments

2 Comments

Comments

2 Comments

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

3 Comments

2 Comments

Comments

2 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related