Algorithm help: Fit a text blurb to its textbox by length

Question

I have a rather unusual problem, and it is hurting my brain.

Problem: Given a textbox of known length, and the text that will go inside it, make the text "fit" by truncating it with room for "..." to fit inside the box. (Context : This is for ASP.NET C#, but I think the algorithm is language agnostic.)

Example : [_________]
Text :     The big brown dog jumped over the red fence.
Solution :[The bi...]

Example : [_________]
Text :     Ferret
Solution :[Ferret___]

Given:

// Returns the number of px (as an int) that the arg text is in length
public int textLength(String theText, float emSize)

Question: What is the simplest and fastest way to do this?

I am afraid to do it by hacking off one character at a time, adding "..." and then checking the length because some of the strings to fit are veeeeery long.

Answer 1

Why start from end? Start from the beginning and add letters (and ...) until it no longer fits. :)

Answer 2

You could do a binary search on the correct length instead, which means you only have to try log(n) sizes.

Oh, also if the text is monospaced (every character is given the width of an em) then it's pretty easy to figure this out programatically:

if str.length * emWidth < textBoxWidth 
   tb.text = str
else
   tb.text = substring(str, 0, round_down(textBoxWidth / emWidth) - 3) + "..."