2

I'd like to design a dictionary which stores a value for a string, such that when two strings are compared, the two corresponding values can be used to determine which string comes first in a dictionary.

For example, the value for "a" should be less than the value for "ab". The value for "z" should be greater than the value for "az". And so on.

I tried googling for this but I wasn't able to find it :( Is there a good way to implement this? I see it is very similar to a decimal system but in base 26. (For example aaa would be like 111, and aaz would be like 11(26).) But that wouldn't work for the case that "z" > "az", since that would be saying (26) > 1(26).

One solution I came up with was to take the length of the largest word (let's say m), and then assign a value by doing 26^m + 26^(m-1) and so on for each letter. However this requires knowing the length of the largest word. Are there any such algorithms that do not require this?

jj172
  • 751
  • 2
  • 9
  • 35
  • How big is the largest string you might want to compare? Also, do the strings contain anything other than letters? What about foreign-language letters such as `ñ` or `œ`? – DodgyCodeException Jan 23 '18 at 22:51
  • 2
    Why do you need the numeric representation? Every coding language I know has built-in comparison functions on strings. – Prune Jan 23 '18 at 22:51
  • 2
    Does it have to be integers? If you use floating point numbers, you could do `int(s[0]) + int(s[1])*26^-1 + ...` – tobias_k Jan 23 '18 at 22:54

1 Answers1

4

This is not possible with only natural numbers/integers because between any two strings there are an infinite number of others (ex. "asdf" < "asdfa" < "asdfaa" < ... < "asdg"), but between any two integers there is only a finite number of integers.

However, as suggested in the comments, if you can use real numbers, you can map a string to char1 + char2/27 + char3/27^2+.... However, for long strings, this will hit the max floating point precision and stop working correctly.

internet_user
  • 3,149
  • 1
  • 20
  • 29