Hướng dẫn cho Xâu đối xứng (Palindrom)


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame


Spoiler Alert


Approach 1

Tạo một xâu t là đảo ngược của xâu s.

isPalindrome(s) = true <=> s = t


Reference AC code | O(n) time | O(n) auxiliary space | string

C++
int main()
{
    string s;
    cin >> s;

    string t = s;
    reverse(t.begin(), t.end());

    cout << (s == t ? "YES" : "NO");    
}

Approach 2

Chạy i từ 1 -> n / 2, nếu vị trí đối xứng của i có giá trị khác nhau thì isPalindrome(s) = false


Reference AC code | O(n) time | O(1) auxiliary space | string

C++
int main()
{
    string s;
    cin >> s;

    for (int i = 0; i < s.size() / 2; ++i)
        if (s[i] != s[s.size() - i - 1])
            return cout << "NO", 0;

    cout << "YES";
    return 0;
}

Approach 3

Cho chạy 2 con trỏ (l từ đầu mảng -> cuối mảng) và (r từ cuối mảng -> đầu mảng).

Nệu tại lr tương ứng nhau có giá trị khác nhau thì isPalindrome(s) = false


Reference AC code | O(n) time | O(1) auxiliary space | string

C++
int main()
{
    string s;
    cin >> s;

    for (int l = 0, r = sz(s) - 1; l < r; l++, r--)
        if (s[l] != s[r])
            return cout << "NO", 0;

    cout << "YES";
    return 0;
}


Bình luận


  • 0
    PY2EVuMinhQuan 7:36 p.m. 11 Tháng 9, 2023

    Python Code:

    str1 = input("nhap x: ")
    if x == x[::-1]:
        print("YES")
    else:
        print("NO")