Letter Combinations of a Phone Number

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

O(4^n · n) n rakam için: her rakam 7 veya 9 olduğunda 4^n dizge olabilir ve her birini yazmak n adım sürer. Çıktının boyutu budur, dolayısıyla 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 ile 9 arasındaki 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 dizgesi alırsın. Rakamların sırasını koruyarak her rakam için bir harf seçtiğinde, tuşların yazabileceği bir dizge elde edersin. Bu tür tüm dizgeleri sözlük sırasına göre döndü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 tüm dizeler, leksikografik sırayla

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 dize 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 harflerin her biri ikinci harflerin her biriyle eşleşir: 3 × 3 = 9 dize; ilk harfin en yavaş değiştiği sırada sıralanır.

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; dolayısıyla 4 × 3 = 12 dizge vardır. w ile başlayan üç dizgenin tamamı, x ile başlayan ilk dizgeden önce gelir.

Ek soru

Diyelim ki yalnızca sözlükte bulunan gerçek kelimelerden oluşan kombinasyonları istiyorsun. Önce tüm 4^n dizeleri 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

Yanıt en fazla 4^n dizge içerir; bu nedenle her çözüm, bunları yazmak için en az bu kadar işlem yapar. Önemli olan, hiçbirini atlamadan veya tekrarlamadan her seçeneği bir kez üretmektir. Bu, her basamak için bir düzey bulunan ve her yaprağın bir yanıt olduğu bir karar ağacı üzerinde geri izlemeyle yapılır.

Karakter dizilerini her seferinde bir basamak oluşturarak oluşturun

Sezgi

İçinde bir boş dize bulunan bir listeyle başlayın ve her seferinde bir rakam ekleyerek listeyi genişletin. "23" için 2 rakamı listeyi a, b, c hâline getirir ve 3, bunların her birini d, e ve f ile genişleterek dokuz dize oluşturur.

Sıralama korunur. Bir rakamı işlemeden önce liste sıralanmışsa, önekleri bu sırayla genişletirsiniz ve her öneki tuş takımındaki harflerle soldan sağa genişletirsiniz: önceki bir önek yine önce gelir ve eşit önekler yeni harfe göre sıralanır.

Yapılan iş, yanıtın boyutuyla orantılıdır; ancak bir düzeyi oluştururken önceki düzeyin tamamı da bellekte kalır.

Algoritma

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 değerini 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ıtlar bir karar ağacının yapraklarıdır. Kök boş dizedir ve her düzey bir sonraki rakamın bir harfini ekler: "23" için kökün a, b, c çocukları vardır ve bunların her birinin d, e, f için çocukları bulunur.

Tek bir arabellek, path ile ağacı derinlik öncelikli dolaş. i düzeyinde, ekleyerek digits[i] içinden bir harf seç, i+1 üzerinde özyinelemeli çağrı yaparak keşfet ve harfi kaldırarak geri al. Geri alma, tek bir arabelleğin ağacın tamamında kullanılmasını sağlar: ad, ae ve af'den sonra, sondan bir eleman silmek path'i a'ya, ardından boş dizeye döndürür ve b için hazırlar. i, digits'in sonuna ulaştığında bir kopyasını kaydet.

Zaman karmaşıklığı yine O(4^n · n)'dir, ancak ek bellek arabellek ve çağrı yığını için O(n)'dir.

Algoritma

Boş bir path ve boş bir result tut.
backtrack(i) tanımla: i, digits uzunluğuna eşitse path'in bir kopyasını kaydet ve dön.
Aksi takdirde, digits[i] tuşundaki her harf için, sırayla: onu path'e ekle, backtrack(i+1) çağır, ardından onu kaldır.
backtrack(0) çağır ve result döndür.

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

Her tuşun üç harfi olduğunu varsaymak. Alfabede (d-2)*3 indeksinden başlayarak üç harf almak, 7'den s harfini çıkarır ve 8'i s harfiyle başlatır. Tuş takımını tablo olarak yazın.
Geri almayı unutmak. path büyümeye devam eder ve "23" için ikinci yanıt ae yerine ade olur.
Bir kopya yerine arabelleği kaydetmek. Python'da result.append(path) aynı listeyi dokuz kez kaydeder ve listenin içi sonunda boşalır.
Bir tuşun harflerini sağdan sola denemek veya yinelemeli sürümde yığından dizeler oluşturmak. Her ikisi de sıralı düzeni bozar.
PHP ve R'de "23" sayı olarak gelebilir. Karakterlerini indekslemeden önce onu metne dönüştürün.

Sıkça sorulan sorular3

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

O(4^n · n) n rakam için: her rakam 7 veya 9 olduğunda 4^n dizge olabilir ve her birini yazmak n adım sürer. Çıktının boyutu budur, dolayısıyla hiçbir çözüm daha iyisini yapamaz. Geri izleme, çıktı dışında O(n) ek alan gerektirir.

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

Tüm yanıtlar aynı uzunluktadır ve derinlik öncelikli bir dolaşım, b’yi seçmeden önce a ile başlayan her dizgeyi tamamlar. Her anahtarın harfleri soldan sağa denendiği sürece aynı durum her düzeyde geçerlidir. Bu sözlük sırasıdır; dolayısıyla sıralama gerekmez.

0 ve 1 rakamlarına ne dersin?

Telefon tuş takımında 0 ve 1 harf içermez ve bu sürüm yalnızca 2 ile 9 arasını kullanır. Bunlar kullanılabilseydi, böyle bir rakamın atlanıp atlanmayacağına ya da yanıtı boş hâle getirip getirmeyeceğine karar vermen gerekirdi. Bir mülakatta, hangisinin istendiğini sor.

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

Test #1

Test #2

Test #3

Argüman

digits = "23"

Beklenen Çıktı

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