sub-strings replacements according to some mapping

Question

Given a string, I need to replace substrings according to a given mapping. The mapping determines where to start the replacement, the length of text to be replaced and the replacement string. The mapping is according to the following scheme:

public struct mapItem
{
    public int offset;
    public int length;
    public string newString;
}

For example: given a mapping {{0,3,"frog"},{9,3,"kva"}} and a string

"dog says gav"

we replace starting at position 0 a substring of the length 3 to the "frog", i.e.

dog - > frog

and starting the position 9 a substring of the length 3 to the "kva", i.e.

gav->kva

The new string becomes:

"frog says kva"

How can I do it efficiently?

Answer 1

You have to take care that replacements take into account the shift produced by preceding replacements. Also using a StringBuilder is more efficient, as is doesn't allocate new memory at each operation as string operations do. (Strings are invariant, which means that a completely new string is created at each string operation.)

var maps = new List<MapItem> { ... };
var sb = new StringBuilder("dog says gav");
int shift = 0;
foreach (MapItem map in maps.OrderBy(m => m.Offset)) {
    sb.Remove(map.Offset + shift, map.Length);
    sb.Insert(map.Offset + shift, map.NewString);
    shift += map.NewString.Length - map.Length;
}
string result = sb.ToString();

The OrderBy makes sure that the replacements are executed from left to right. If you know that the mappings are provided in this order, you can drop the OrderBy.

Another simpler way is to begin with the replacements at the right end and work backwards, so that the character shifts do not alter the positions of not yet executed replacements:

var sb = new StringBuilder("dog says gav");
foreach (MapItem map in maps.OrderByDescending(m => m.Offset)) {
    sb.Remove(map.Offset, map.Length);
    sb.Insert(map.Offset, map.NewString);
}
string result = sb.ToString();

In case the mappings are already ordered in ascending order, a simple reverse for-statement seems appropriate:

var sb = new StringBuilder("dog says gav");
for (int i = maps.Count - 1; i >= 0; i--) {
    MapItem map = maps[i];
    sb.Remove(map.Offset, map.Length);
    sb.Insert(map.Offset, map.NewString);
}
string result = sb.ToString();