Xâu đối xứng (Palindrom)

Tác giả:

Dạng bài

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Cho một xâu kí tự, hãy kiểm tra tính đối xứng của nó. Một xâu kí tự được gọi là xâu đối xứng nếu ta đọc xâu này từ trái sang phải hoặc từ phải sang trái là như nhau.

Input

Một xâu ký tự \(S\).

Output

In ra \(YES\) nếu \(S\) là xâu đối xứng, ngược lại in ra \(NO\).

Constraints

\(1 \leq S.size() \leq 255\)

Example

Test 1

Input

abccba

Output

YES

Test 2

Input

abcccc

Output

NO

Bình luận

`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 l và r 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;
}

6 bình luận nữa