Satu lagi cara untuk memeriksa palindrom

Pada hari ini, saya sedang menatal ke Linkedin dan Twitter, dan melihat cabaran pengekodan yang sangat biasa: semak sama ada rentetan ialah palindrom.

Ia satu cabaran yang sangat mudah. Palindrom ialah perkataan atau frasa yang boleh dibaca sama ke dalam dan ke belakang. Sama seperti:

• tesset
• mak
• biaib

dan seterusnya.

Tetapi pendekatan umum yang diikuti orang adalah seperti ini:

Dalam erti kata lain, mereka mengambil rentetan asal dan kemudian membalikkannya, kemudian membandingkannya dengan rentetan asal.
Ini pendekatan yang sangat sah, tetapi saya ingin mencadangkan pendekatan yang bijak untuknya.

Pastikan anda perlu menghasilkan peruntukan baharu untuk rentetan, kemudian bandingkan char demi char. Cara ia boleh menjadi lebih mencabar ialah, bagaimana untuk melakukannya menggunakan lebih banyak memori O(1) dan kurang membuat perbandingan?

Biar saya jelaskan perkara ini dengan lebih baik.

Pendekatan yang lebih baik untuk menangani masalah ini adalah dengan menggunakan pendekatan dua mata.

Sebuah rentetan tidak lebih daripada tatasusunan char, dan kita boleh melaluinya char demi char, dan membuat traversal dan perbandingan terhadap mana-mana char array.

Mari kita memfaktorkannya semula menggunakan pendekatan baharu menggunakan dua penuding.
Perkara pertama yang perlu kita buat ialah mengambil kepingan rune daripadanya:

  r := []rune(str);

String dalam Go adalah baca sahaja, jadi pada asasnya, rentetan itu tidak boleh diubah dan tidak boleh ditukar. Potongan rune, jika tidak boleh ditukar, dan kemudian, penukaran antara kedua-duanya membuat salinan bait rentetan, tetapi kemudian, kami tidak membuat salinan lain di sini, kerana kami akan meneruskan dalam bingkai tindanan yang sama, dan kami tidak akan menghasilkan rentetan baharu.

Selepas itu, kita akan memulakan gelung, dengan penuding pada permulaan rune dan satu lagi dari hujung, dan kita akan melintasinya sehingga satu melintasi yang lain. Kami akan membuat perbandingan di sini:

func isPalindrome(str string) bool {
    r := []rune(str)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        if r[i] != r[j] {
            return false
        }
    }
    return true
}

Dengan cara itu, jika perbandingan berjalan lancar, dan semua aksara adalah sama, maka ia adalah palindrom. Jika tidak, ia kembali palsu serta-merta.

Atas ialah kandungan terperinci Satu lagi cara untuk memeriksa palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!