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

问题:

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)

回答1:

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())

回答2:

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

回答3:

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
    }
}

回答4:

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.

回答5:

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.

回答6:

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).