2026-11-15
natural_cmp.rs
use std::cmp::Ordering;
fn natural_cmp(a: &str, b: &str) -> Ordering {
}
英小文字と数字だけからなる2つの名前を比べ、a が b より前なら Less、後ろなら Greater、同じ位置なら Equal を返す natural_cmp を書いてください。名前は、数字の連続とそれ以外の1文字ずつに区切って先頭から比べます。数字の連続どうしは0以上の整数として比べ、桁数に上限はありません。数として等しい連続(007 と 7)は等しいとみなします。それ以外の組は文字コードの順で比べ、片方の名前が先に尽きたらそちらを前にします。
入力例 1
natural_cmp("file2", "file10")
出力例 1
Less
入力例 2
natural_cmp("v99999999999999999999", "v100000000000000000000")
出力例 2
Less
入力例 3
natural_cmp("img007", "img7")
出力例 3
Equal
Reference
Reference
use std::cmp::Ordering;
fn natural_cmp(a: &str, b: &str) -> Ordering {
key(a).cmp(&key(b))
}
fn key(mut s: &str) -> Vec<(bool, usize, &str)> {
let mut k = Vec::new();
while !s.is_empty() {
let n = s.find(|c: char| !c.is_ascii_digit()).unwrap_or(s.len());
if n == 0 {
k.push((true, 1, &s[..1]));
s = &s[1..];
} else {
let digits = s[..n].trim_start_matches('0');
k.push((false, digits.len(), digits));
s = &s[n..];
}
}
k
}
入力例 2 の数は u64 の上限(約 1.8 × 1019)を超えるので、数字の連続を整数に直して比べる方法は使えません。整数に直さなくても、先頭の0を除いた数字の並びなら、桁数の多い方が大きい数です。桁数が同じなら、上の桁から順に比べて最初に違った桁で大小が決まり、これは文字列を辞書式に比べるのと同じです。そこで数字の連続を、先頭の0を除いて「桁数、数字の並び」の組にすれば、組の比較がそのまま数の比較になります。掲載したのは参考実装で、唯一の正解ではありません。
参考実装は、この組を名前全体に広げます。key は名前を区切り、数字の連続を (false, 桁数, 0を除いた並び) に、それ以外の1文字を (true, 1, その文字) にした Vec を作ります。Vec とタプルの比較は先頭の要素から順に比べる辞書式なので、2つの key を cmp で比べるだけで、区切りを先頭から比べる処理も、先に尽きた方を前にする処理も済みます。数字の連続と英小文字の組は、先頭の bool の false < true で数字の方が前になり、文字コードで '0' から '9' が 'a' より小さいことと一致します。
入力例 2 では、"v" が等しく、続く数字の連続は 20 桁と 21 桁なので Less です。入力例 3 では、"007" も "7" も0を除くと (false, 1, "7") になり、Equal になります。0 だけの連続は空の並びになりますが、"0" と "00" がどちらも桁数 0 で等しくなり、どの正の数よりも前に来るので、そのままで正しく比べられます。