Вступ

Маніпулювання рядками є основним поняттям в програмуванні, а підрахунок пар префіксів та суфіксів є цінним завданням для перевірки ваших навичок. Це завдання пропонує нам знайти пари рядків, де один рядок є одночасно префіксом та суфіксом іншого. Хоча концепція досить проста, для реалізації рішення потрібно добре розуміти операції з рядками та використовувати вкладені ітерації.

Умови завдання

Вам надано масив рядків, words. Потрібно підрахувати всі пари індексів (i, j), де:

1. i < j
2. words[i] є одночасно префіксом та суфіксом для words[j].

Крок 1: Перевірка чи є рядок префіксом і суфіксом

Створимо функцію isPrefixAndSuffix, яка перевіряє, чи є рядок префіксом та суфіксом іншого рядка:

def isPrefixAndSuffix(str1, str2)  
 return false if str1.length > str2.length  
 prefix = str2[0...str1.length]  
 suffix = str2[-str1.length..-1]  
 prefix == str1 && suffix == str1  
end

Крок 2: Підрахунок пар префіксів і суфіксів

Використовуючи вкладений цикл, ітеруємо через всі пари індексів (i,j), де i < j:

def countPrefixSuffixPairs(words)  
 count = 0  
 words.each_with_index do |word, i|  
 words.each_with_index do |wrd, j|  
 next if i >= j # Переконайтесь, що i < j  
 count += 1 if isPrefixAndSuffix(word, wrd)  
 end  
 end  
 count  
end

Приклад розв'язку

Приклад 1:

Вхід: words = ["a", "aba", "ababa", "aa"]

Кроки:

1. Починаємо з i = 0, j = 1. Перевіряємо, чи є "a" префіксом та суфіксом для "aba".

• Префікс: "aba"[0] == "a".
• Суфікс: "aba"[-1] == "a".
• Результат: Так. Збільшуємо лічильник.

1. Повторюємо для i=0, j=2, i=0, j=3 та i=1, j=2

• Всі умови виконуються.

Вихід: 4.

Пояснення коду

1. isPrefixAndSuffix:

• Перевіряє, чи не є str1 довшим за str2.
• Витягує префікс та суфікс за допомогою зрізів.
• Порівнює їх з str1.

2. Вкладений цикл:

• Ітерує через кожну можливу пару індексів.
• Пропускає неприпустимі пари, де i ≥ j.
• Збільшує лічильник, коли isPrefixAndSuffix повертає true.

Ефективність

1. Часова складність:

• Рішення використовує два вкладених цикли, що дає складність O(n²), де n — це довжина масиву words.
• Для кожної пари зрізи виконуються за O(k), де k — це довжина рядків.

2. Просторова складність:

• Просторова складність O(1), оскільки ми використовуємо лише кілька змінних для обчислення результату.

  Просторова складність:

• O(1), оскільки не використовуються додаткові структури даних.

Цей підхід є ефективним з огляду на обмеження (n≤50, k≤10).

Тестування рішення

Приклад 1:

words = ["a", "aba", "ababa", "aa"]  
puts count_prefix_suffix_pairs(words) # Вихід: 4

Приклад 2:

words = ["pa", "papa", "ma", "mama"]  
puts count_prefix_suffix_pairs(words) # Вихід: 2

Приклад 3:

words = ["abab", "ab"]  
puts count_prefix_suffix_pairs(words) # Вихід: 0

Висновок

Це рішення демонструє, як поетапно вирішувати поширену задачу маніпулювання рядками. Чітко визначаючи допоміжні функції та ітеруючи через вхідні дані систематично, ми забезпечуємо правильність та зрозумілість рішення.

Такі задачі тестують ваше розуміння рядків і допомагають покращити навички налагодження та оптимізації. Спробуйте застосувати цей підхід до подібних задач для додаткової практики!

Щасливого кодування! 🚀

Перекладено з: Solving the Count Prefix and Suffix Pairs I Problem in Ruby: A Step-by-Step Guide