Letter Combinations of a Phone Number

Q: Telefon Numarasının Harf Kombinasyonlarının zaman karmaşıklığı nedir?

n basamak için O(4^n · n) olur: her basamak 7 veya 9 olduğunda 4^n dize olabilir ve her birini yazmak n adım sürer. Yalnızca üç harfli tuşlarla O(3^n · n) olur. Çıktının boyutu bu olduğundan hiçbir çözüm daha iyisini yapamaz. Geri izleme, çıktı dışında O(n) ek alan gerektirir.

OrtaGeri izleme

+10

Telefon tuş takımında 2'den 9'a kadar her rakam birkaç harfi temsil eder: 2, abc; 3, def; 4, ghi; 5, jkl; 6, mno; 7, pqrs; 8, tuv ve 9, wxyz.

Bir digits dizeniz var. Rakamların sırasını koruyarak her rakam için bir harf seçtiğinizde, tuşların yazabileceği bir dize elde edersiniz. Bu tür dizelerin tamamını sözlük sırasına göre döndürün. "23" için, "ad" ile "cf" arasında dokuz dize vardır.

Fonksiyon

letterCombinations(digits: string) → string-array

digitsstring: basılan rakamlar, her biri 2 ile 9 arasında
Döndürürstring-array: tuşların yazabileceği her dizge, sözlük sırasına göre

Kısıtlar

1 ≤ digits.length ≤ 4
digits içindeki her karakter 2 ile 9 arasında bir rakamdır.
Yanıt en fazla 4⁴ = 256 dizge içerir.

Örnekler

Girdi: digits = "23"
Çıktı: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Açıklama: 2, a, b, c harflerini ve 3, d, e, f harflerini sunar. İlk harf, ikinci harflerin her biriyle eşleşir; böylece 3 × 3 = 9 dize elde edilir ve bunları ilk harf en yavaş değişecek şekilde listelemek sıralı kalmalarını sağlar.

Girdi: digits = "94"
Çıktı: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Açıklama: 9 dört harften, 4 ise üç harften oluşur; bu yüzden 4 × 3 = 12 dize vardır. w ile başlayan üç dizenin tamamı, x ile başlayan ilk dizeden önce gelir.

Gönderirken +14 gizli test

Ek soru

Sözlükte bulunan gerçek sözcüklerden oluşan kombinasyonları istiyorsan, önce tüm 4^n dizelerini oluşturmaktan nasıl kaçınabilirsin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Burada hiçbir şey atlanamaz: yanıtın kendisi en fazla 4^n dizge içerir, bu yüzden her doğru çözüm bunları yazmak için en az bu kadar iş yapar. Problemin sınadığı şey, seçenekler kümesini hiçbirini atlamadan veya yinelemeden sistematik olarak üretip üretemediğindir. Bu, en yalın hâliyle geri izleme yöntemidir: her rakam için bir düzeyi olan, derinlik öncelikli dolaşılan bir karar ağacında her yaprak bir yanıttır.

Metin dizelerini her seferinde bir rakam ekleyerek oluşturun

Sezgi

Yanıtları her seferinde bir basamak ekleyerek oluştur. Bir boş dize içeren bir listeyle başla. "23" için 2 basamağı bunu a, b, c hâline getirir. Ardından 3 basamağı, bu üç dizenin her birini d, e ve f ekleyerek genişletir; böylece uzunluğu 2 olan dokuz dize elde edilir. Son basamaktan sonra liste tüm yanıtları içerir.

Sıralama kendiliğinden oluşur. Bir basamak eklemeden önce listenin sıralı olduğunu varsayalım. Önekleri aynı sırayla genişletirsin ve her öneki, tuşun harflerini soldan sağa ekleyerek genişletirsin. Daha önce gelen bir öneke sahip dize yine önce gelir; aynı öneke sahip iki dize ise yeni harfe göre sıralanır; bu da sözlük sıralamasıdır.

Maliyet, yanıtın boyutudur. n basamakla son listede, uzunluğu n olan en fazla 4^n dize bulunur; önceki listelerin tümü birlikte bunun en fazla yarısı kadar dize içerir ve bunların hepsi daha kısadır. Dezavantajı ise bellektir: Bir düzeyi oluştururken, atacağın tüm kısa önekler de dâhil olmak üzere önceki düzeyin tamamı bellekte tutulur.

Algoritma

Tek bir boş önek olan combos = [""] ile başla.
Her rakam için yeni bir liste oluştur: combos içindeki her önek ve o rakamın tuşundaki her harf için prefix + letter ekle.
combos öğesini yeni listeyle değiştir.
Son rakamdan sonra combos değerini döndür.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

Karar ağacında geri izleme

Sezgi

Yanıtı bir karar ağacı olarak düşün. Kök, boş bir dizedir. "23" için üç çocuğu vardır: 2'nin her harfi için bir tane olmak üzere a, b ve c. Bunların her birinin de kendine ait üç çocuğu vardır; 3'ün her harfi için bir tane. Ağaçta her rakam için bir seviye bulunur ve ad ile cf arasındaki dokuz yaprak, yanıtların tam olarak kendisidir.

Geri izleme, bu ağacı tek bir arabellek olan path ile derinlik öncelikli olarak dolaşır. i seviyesinde digits[i] içinden bir harf ekleyerek seçer, i+1 üzerinde özyinelemeli çağrı yaparak altındaki her şeyi keşfeder ve harfi kaldırarak seçimi geri alır. Geri alma, tek bir arabelleğin tüm ağaç için kullanılmasını sağlar: ad, ae ve af kaydedildikten sonra, harfi çıkarmak path'i önce a'ya, sonra boş dizeye döndürür; böylece b için hazır olur. i, digits'in uzunluğuna eşit olduğunda, arabellek tam bir yanıttır ve bunun bir kopyasını kaydedersin.

Her seviyede harfleri soldan sağa denemek, yaprakları sözlük sırasıyla ziyaret eder; bu nedenle çıktıyı sıralamak gerekmez. Bu problemde her dal bir yanıtla sona erdiğinden budanacak bir şey yoktur; ağaç yalnızca 4 seviye derinliğindedir ve en fazla 256 yaprağı vardır. Yanıtları yazma işleminin maliyeti yine O(4^n · n)'dir; ancak ek bellek, tüm bir önekler seviyesi yerine arabellek ve çağrı yığını için O(n)'dir. Aynı seç, keşfet, geri al döngüsü alt kümeler, permütasyonlar, kombinasyon toplamı ve sözcük arama problemlerini çözer.

Algoritma

Boş bir path ve boş bir result tutun.
backtrack(i) tanımlayın: i, digits uzunluğuna eşitse path'in bir kopyasını kaydedin ve geri dönün.
Aksi hâlde, digits[i] tuşundaki her harf için sırasıyla: harfi path'e ekleyin, backtrack(i+1) çağrısını yapın, ardından harfi kaldırın.
backtrack(0) çağrısını yapın ve result döndürün.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

Tuzaklar ve uç durumlar

Aramanın kendisi kısadır; bu yüzden hataların çoğu tuş takımından veya paylaşılan arabellekten kaynaklanır.

Her tuşun üç harfi olduğunu varsaymak. 7, pqrs; 9 ise wxyz harflerini içerir. Bu nedenle alfabeden (d-2)*3 indeksinden başlayarak üç harf almak, 7'deki s harfini atlar ve 8'i t yerine s ile başlatır. Tuş takımını bir tablo olarak yazın.
Geri almayı unutmak. Özyinelemeli çağrıdan sonra harfi kaldırmazsanız path büyümeye devam eder ve "23" için ikinci yanıt ae yerine ade olur.
Arabellek yerine kopyasını kaydetmek. Python'da result.append(path) aynı listeyi dokuz kez saklar ve sonunda liste boş olur. Kaydederken yeni bir dizge oluşturmak için listeyi birleştirin.
Sıralamayı kaybetmek. Bir tuşun harflerini sağdan sola denemek veya yinelemeli sürümde dizgeleri bir yığından oluşturmak, yanıtları problemin istediği sıralı düzenden farklı bir sırada verir.
Basamak dizgesinin sayı olarak okunması. PHP ve R gibi gevşek türlendirilmiş dillerde "23" size 23 sayısı olarak gelebilir. Karakterlerine indekslemeden önce onu metne dönüştürün.

Sıkça sorulan sorular4

Telefon Numarasının Harf Kombinasyonlarının zaman karmaşıklığı nedir?

n basamak için O(4^n · n) olur: her basamak 7 veya 9 olduğunda 4^n dize olabilir ve her birini yazmak n adım sürer. Yalnızca üç harfli tuşlarla O(3^n · n) olur. Çıktının boyutu bu olduğundan hiçbir çözüm daha iyisini yapamaz. Geri izleme, çıktı dışında O(n) ek alan gerektirir.

Harf Kombinasyonları problemini özyineleme kullanmadan çözebilir misin?

Evet. Yanıtları seviye seviye oluştur: boş bir dizeyle başla ve her rakam için elindeki her dizgeyi o tuştaki her harfle genişlet. Aynı miktarda iş yapar ve derinlik öncelikli yerine genişlik öncelikli olarak dolaşılan aynı ağaçtır. Bellekte tüm bir önek seviyesini tutarken, özyineleme yalnızca rakam sayısı kadar derin bir yığına ihtiyaç duyar.

Geri izleme kombinasyonları neden sıralı olarak döndürür?

Tüm yanıtlar aynı uzunluktadır ve derinlik öncelikli bir dolaşma, ilk düzeyde b'yi seçmeden önce a ile başlayan her dizgeyi tamamlar. Her anahtarın harfleri soldan sağa denendiği sürece bu durum her düzeyde geçerlidir. Bu tam olarak sözlük sıralamasıdır, dolayısıyla sıralama yapmaya gerek yoktur.

0 ve 1 rakamlarına ne dersin?

Telefon tuş takımında 0 ve 1'in harfi yoktur ve bu problem sürümü yalnızca 2'den 9'a kadar olan rakamları kullanır. Bu rakamlar da kullanılabilseydi, böyle bir rakam seçilebilecek harf sunmadığından, bu rakamın atlanıp atlanmayacağına ya da yanıtın boş olmasına mı yol açacağına karar vermeniz gerekirdi. Bir mülakatta, kodlamaya başlamadan önce hangisinin istendiğini sorun.

Python

def letterCombinations(digits):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

digits = "23"

Beklenen

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]