Lexicographically larger strings

2019-07-18 13:54发布

问题:

I'm trying to understand the concept of lexicographically larger or smaller strings. My book gives some examples of strings that are lexicographically larger or smaller than each other and an intermediary string that is between the two in size.

string 1: a
string 2: c
intermediary string: b

string 1: aaa
string 2: zzz
intermediary string: yyy

string 1: abcdefg
string 2: abcdefh
intermediary string: (none)

I'm not sure what the requirement is for a string to be lexicographically in between the two strings. Is it that every letter of the intermediary string has to have a larger ASCII value than the corresponding letter of the first string and smaller ASCII value of the corresponding letter of the second string?

For example, "bcdefg" is the intermediary string between "abcdef" and "cdefgh". Can "stuvx" be the intermediary between "stuvw" and "stuvy"?

回答1:

Lexicographical ordering simply means dictionary ordering. I say "simply" but there may actually be all sorts of wonderful edge cases such as how you treat apostrophes, what you do with diphthongs, whether you "fold" accented letters into the unaccented ones, such as transforming {À,Á,Â,Ã,Ä} -> A. All these rules on how you collate letters will affect the ordering of words as well.

English is fairly easy if you restrict yourself to the twenty-six actual letters of the alphabet. You can consider a word to be "lesser" than another word if, in the first character position that is different between the two, the character from the first word comes before that of the second.

And, in fact, there is a solution to the third option provided it doesn't have to be the same length as the others, that of:

string 1: abcdefg
string 2: abcdefh
intermediary string: abcdefga