7

I am writing a spell corrector that gives suggestions to the user. To do this, I am using words one and two edit distance away. There are four techniques:

  • deleting one letter of the word,
  • transposing two neighboring letters,
  • alteration of one letter of the word, and
  • inserting one letter to the word.

Some of these require many iterations through the word, and doing things like swapping two letters, or adding a letter in the middle of a string.

I know String are immutable in java, and that insert from string builder might create copies of the string as necessary, so I was wondering if an array of char would make this any faster.

Sнаđошƒаӽ
  • 16,753
  • 12
  • 73
  • 90
Felipe Centeno
  • 2,911
  • 1
  • 21
  • 39
  • @AndyTurner It seems to be a good answer :) – Filipe Borges May 05 '16 at 14:11
  • It is also worth mentioning that the Java compiler is smart enough to replace string operations (like the + operator) with StringBuilder, often making these kind of decisions unnecessary. see also http://stackoverflow.com/questions/1532461/stringbuilder-vs-string-concatenation-in-tostring-in-java – Sharon Ben Asher May 05 '16 at 14:27

1 Answers1

11

It is very hard to say - without more context - which of various approaches will be the fastest. (Or even if the difference in speed is relevant; or that speed is the most important metric).

You would need to benchmark the various approaches for your situation.

StringBuilder is just a wrapper around a char[], adding functionality like resizing the array as necessary; and moving elements when you insert/delete etc.

It might be marginally faster to use the char[] directly for some things, but you'd lose (or have to reimplement) a lot of the useful functionality.

Andy Turner
  • 137,514
  • 11
  • 162
  • 243