▲

3

▼

😄 Проверка возможности выравнивания строк за 1 своп

leetcoder, изменено 07-02-2025 , 240

Ссылка на задачу – 1790. Check if One String Swap Can Make Strings Equal.

Описание задачи 😊

Даны две строки s1 и s2 равной длины. Необходимо определить, можно ли сделать строки равными, совершив не более одного обмена символов в одной из строк.
Обмен — это операция, когда выбираются два индекса в строке и символы на этих позициях меняются местами.

Идея 😊

Основная идея заключается в поиске позиций, на которых символы в строках различаются.

• Если различий нет, строки уже равны.
• Если различия ровно в двух позициях, то проверяем, поможет ли один обмен исправить ситуацию.
• В остальных случаях (1 или более 2 отличий) сделать строки равными одним обменом невозможно.

Детали подхода 🚀

1. Сбор различающихся индексов:
   • Пройдемся по всем индексам строк и соберем в вектор те индексы, на которых символы в s1 и s2 различаются.
     При этом достаточно собрать максимум 3 индекса.
2. Проверка случаев:
   • Нет различий: Если вектор пуст, строки равны.
   • Два различия: Если в векторе ровно два индекса, проверяем: соответствует ли обмен символами в этих позициях условию
     (s1[i] == s2[j] и s1[j] == s2[i])
   • Любой другой случай ❌: Если индекс один или их больше двух, один обмен не сможет выровнять строки.

Асимптотика ⚡

• Время: O(n) — один проход по индексам строк.
• Память: O(1) — в худшем случае хранится не более 3 индексов независимо от размера входных данных.

Исходный код 💻

impl Solution {
    pub fn are_almost_equal(s1: String, s2: String) -> bool {
        let n = s1.len();
        let s1_bytes = s1.as_bytes();
        let s2_bytes = s2.as_bytes();

        // Collect up to 3 indices where characters differ.
        let mismatch_indices: Vec<_> = (0..n)
            .filter(|&i| s1_bytes[i] != s2_bytes[i])
            .take(3)
            .collect();

        match mismatch_indices[..] {
            [] => true, // No mismatches: strings are equal.
            [i, j] => s1_bytes[i] == s2_bytes[j] && s1_bytes[j] == s2_bytes[i],
            _ => false, // 1 mismatch or >2 mismatches: cannot be fixed by one swap.
        }
    }
}

Tags: #rust #algorithms #strings