The run time for the edit distance calculations is trivial, but I'd be concerned that the results will be poor. Character-by-character will be noisy; I'd be amazed if you got any exact matches. Word-by-word will be subject to the vagaries of erroneously hearing a plural, homophones, etc, etc.
That said, nothing wrong with trying the simplest possible thing first. If the results aren't good enough, though next I'd try:
- Splitting the string up, run a simple stemming algorithm on the words, and then do the edit distance calculations. https://pypi.python.org/pypi/stemming/1.0 for example.
- If that doesn't produce clean enough results, I'd fall back to the vector space document model which you could easily implement for your purposes, in 20-30 lines of most high level languages. (Or pull out the heavy guns and shove it into Lucene.)