Büyük-küçük harf varyantları
Görev tanımı
Problem
Bir string harfleri ve rakamları karışık tutuyor. Her harf küçük ya da büyük harfle yazılabilir, rakamlar ise hiç değişmez. Bu şekilde üretebileceğin her string'i döndür. Soldan sağa her harf için küçük harf seçeneği büyük harf seçeneğinden önce gelecek şekilde listele.
Örnekler
Input: s = "a1b"
Output: ["a1b", "a1B", "A1b", "A1B"]
Neden: iki harf, her birine iki seçenek, dört string
Input: s = "3Z"
Output: ["3z", "3Z"]
Neden: harfin orijinal hali önemli değil, iki biçim de listelenir
Input: s = "42"
Output: ["42"]
Neden: edge case: hiç harf yoksa tam olarak bir string var, girdinin kendisi
İpuçları
0 / 3
String'i her seferinde bir konum dolaş ve her konumun gerçekte kaç seçeneği olduğunu sor. Rakamlar ve harfler bu soruyu farklı cevaplar.
Bu bir karar ağacı: harfler iki dala ayrılır, rakamlar doğrudan geçer. Yaprak sayısı 2 üzeri harf sayısıdır.
Konum üzerinde özyinele. Bir harfte küçük biçimini paylaşılan bir buffer'a yaz ve özyinele, sonra üzerine büyük biçimini yaz ve yeniden özyinele. Bir rakamda yalnız özyinele. Konum sona ulaşınca birleştirilmiş buffer'ı kaydet.
- Hedef zaman
- O(n · 2^L)
- Hedef alan
- O(n · 2^L)
Kısıtlar
- the string holds only letters and digits
Çözüm
Her harf tam iki dallı, al ya da alma tarzı bir karardır; her rakam da tek dallı bir seviyedir. Bu yüzden özyineleme (recursion) derinliği string'in uzunluğudur ve yapraklar cevaplardır. Tek bir buffer (tampon) mevcut string'i tutar; her dal derine inmeden önce kendi konumunun üzerine yazar, açık bir geri alma adımına gerek olmamasının sebebi bu. Önce küçük harf biçimini denemek istenen sırayı verir. n uzunluğundaki bir string'de L harf varsa n uzunluğunda 2 üzeri L sonuç vardır; zaman O(n · 2^L), özyineleme derinliği O(n).
def case_variants(s):
out, path = [], list(s)
def build(i):
if i == len(s): # every position is decided
out.append("".join(path))
return
if s[i].isalpha():
for ch in (s[i].lower(), s[i].upper()): # two branches
path[i] = ch # overwriting doubles as the undo
build(i + 1)
else:
build(i + 1) # a digit has a single branch
build(0)
return out
print(case_variants("a1b")) # -> ['a1b', 'a1B', 'A1b', 'A1B']
print(case_variants("3Z")) # -> ['3z', '3Z']
print(case_variants("42")) # -> ['42']Kodda değil de fikirde mi takıldın? Alt kümeler bunu anlatıyor.