Tutarlı yeniden adlandırma kontrolü
Görev tanımı
Problem
Biri karakterler yeniden adlandırılarak diğerine çevrilebiliyorsa iki metin parçası aynı şekle sahiptir. Yeniden adlandırma iki yönde de tutarlı olmalı: bir karakterin her geçişi aynı karşılığa eşlenir ve iki farklı karakter aynı karşılığı paylaşamaz. Böyle bir yeniden adlandırmanın olup olmadığına karar ver.
Örnekler
Input: a = "egg", b = "add"
Output: True
Neden: e a'ya, g de d'ye tutarlı biçimde dönüşüyor
Input: a = "foo", b = "bar"
Output: False
Neden: o hem a'ya hem r'ye dönüşmek zorunda kalırdı
Input: a = "ab", b = "aa"
Output: False
Neden: edge case: iki karakter aynı karşılığa çökemez
İpuçları
0 / 3
İki metinde aynı konumdaki karakterler her zaman birlikte eşleşir; yani bütün soru, bu eşleşmelerin birbiriyle hiç çelişip çelişmediği.
Eşleşmeleri ilerledikçe kaydetmek kontrolü bir aramaya çevirir. Tek bir map yetmez, çünkü çelişkileri yalnız bir yönde yakalar.
Her taraftan diğerine birer tane olmak üzere iki map tut. Her konumda, map'lerden biri karakteri için zaten bir kayıt tutuyorsa mevcut eşiyle uyuşmalı; değilse yeni kaydı yaz. İki yönden birinde bir uyuşmazlık kontrolü hemen bitirir.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Çözüm
İki metni birlikte dolaşmak karakterleri konum konum eşler ve geçerli bir yeniden adlandırma, hiçbir çiftin önceki bir çiftle çelişmemesi demektir. Bir değil iki map gerekir: ileri map bir karakterin iki farklı şekilde yeniden adlandırılmasını, geri map de iki karakterin aynı karşılığa çökmesini yakalar. İlk görüşte kaydetmek ve sonrasında karşılaştırmak iki kontrolü tek geçişte yapar. Zaman ortalamada O(n), farklı karakterler için alan O(k).
def has_consistent_renaming(a, b):
if len(a) != len(b):
return False
forward, backward = {}, {} # a -> b and b -> a pairings seen so far
for x, y in zip(a, b):
# setdefault records a new pairing and returns the one already stored
if forward.setdefault(x, y) != y or backward.setdefault(y, x) != x:
return False
return True
print(has_consistent_renaming("egg", "add")) # -> True
print(has_consistent_renaming("foo", "bar")) # -> False
print(has_consistent_renaming("ab", "aa")) # -> FalseKodda değil de fikirde mi takıldın? Hash tablosu temelleri bunu anlatıyor.