Sətir məsələləri alqoritmlərin sevimli sınaq meydanıdır: sadə görünür, amma qiymət modelini dəqiq bilmək tələb edir. Bu mövzuda sətri normallaşdırmağı, palindromu və anaqramı yoxlamağı, anaqramları qruplaşdırmağı və ən uzun palindromu tapmağı öyrənirik.
Qiymət modeli
Python-da str dəyişməzdir. Hər dilim, lower(), replace() yeni sətir yaradır və O(n) vaxt, O(n) yaddaş aparır. s[i] və len(s) isə O(1)-dir. sorted(s) simvolların siyahısını O(n log n)-də qaytarır, Counter isə O(n)-də sayır. Gizli xərc: s += c dövrdə bəzən O(n^2) ola bilər (bu barədə növbəti mövzuda).
Normallaşdırma və palindrom
Palindrom hər iki istiqamətdə eyni oxunan sətirdir. Real mətnlərdə boşluq, durğu işarələri və registr müqayisəni pozur, ona görə əvvəlcə normallaşdırırıq: yalnız hərf-rəqəmləri saxlayıb kiçik hərfə çeviririk. Sonra t == t[::-1].
