336. Palindrome Pairs

public class Solution {
    public IList<IList<int>> PalindromePairs(string[] words) {
        var pairs = new List<IList<int>>();
        
        for (int i = 0; i < words.Length; i++) {
            for (int j = 0; j < words.Length; j++) {
                if (i == j) continue;
                string combined = words[i] + words[j];
                if (combined == new string(combined.Reverse().ToArray())) {
                    pairs.Add(new List<int> { i, j });
                }
            }
        }
        
        return pairs;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<int>> PalindromePairs(vector<string> words) {
        var pairs = new List<vector<int>>();
        
        for (int i = 0; i < words.size(); i++) {
            for (int j = 0; j < words.size(); j++) {
                if (i == j) continue;
                string combined = words[i] + words[j];
                if (combined == new string(combined.Reverse().ToArray())) {
                    pairs.push_back(new List<int> { i, j });
                }
            }
        }
        
        return pairs;
    }
}

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {

        List<List<Integer>> pairs = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i == j) continue;
                String combined = words[i].concat(words[j]);
                String reversed = new StringBuilder(combined).reverse().toString();
                if (combined.equals(reversed)) {
                    pairs.add(Arrays.asList(i, j));
                }
            }   
        }

        return pairs;
    }
}

var palindromePairs = function(words) {
    let pairs = [];
    
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words.length; j++) {
            if (i === j) continue;
            let combined = words[i] + words[j];
            if (combined === combined.split('').reverse().join('')) {
                pairs.push([i, j]);
            }
        }
    }
    
    return pairs;
};

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        pairs = []
        
        for i in range(len(words)):
            for j in range(len(words)):
                if i == j:
                    continue
                combined = words[i] + words[j]
                if combined == combined[::-1]:
                    pairs.append([i, j])
        
        return pairs

func palindromePairs(words []string) [][]int {
    var pairs [][]int
    
    for i := 0; i < len(words); i++ {
        for j := 0; j < len(words); j++ {
            if i == j {
                continue
            }
            combined := words[i] + words[j]
            if combined == reverseString(combined) {
                pairs = append(pairs, []int{i, j})
            }
        }
    }
    
    return pairs
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

Algorithm

Esempio:

Input: words = ["abcd","dcba","lls","s","sssll"]

Output: [[0,1],[1,0],[3,2],[2,4]]

Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

👨‍💻

Algoritmo:

Инициализация и подготовка данных:

Создайте структуру для хранения результатов (список пар индексов).

Создайте словарь для хранения слов и их индексов, чтобы ускорить поиск.

Итерация по всем парам слов и проверка:

Пройдите по всем парам слов в arrayе words, используя два вложенных цикла.

Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная stringa своей обратной версии.

Добавление найденных пар в результат:

Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов.

return итоговый список всех найденных пар.

😎