Palindrome pairs

Array Hash Table String Trie

37.0% acceptance

Jan 12, 2026

4624

476

You are given a 0-indexed array of unique strings words. A palindrome pair is a pair of integers (i, j) such that: 0 <= i, j < words.length, i != j, and words[i] + words[j] (the concatenation of the two strings) is a palindrome. Return an array of all the palindrome pairs of words. You must write an algorithm with O(sum of words[i].length) runtime complexity.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn palindrome_pairs(words: Vec<String>) -> Vec<Vec<i32>> {
    use std::collections::HashMap;
    
    fn is_palindrome(bytes: &[u8]) -> bool {
      let n = bytes.len();
      for i in 0..n / 2 {
        if bytes[i] != bytes[n - 1 - i] {
          return false;
        }
      }
      true
    }
    
    let mut word_map: HashMap<&str, usize> = HashMap::new();
    for (i, word) in words.iter().enumerate() {
      word_map.insert(word.as_str(), i);
    }
    
    let mut result = Vec::new();
    
    for (i, word) in words.iter().enumerate() {
      let word_bytes = word.as_bytes();
      let rev: String = word.chars().rev().collect();
      
      // Check for exact reverse match
      if let Some(&j) = word_map.get(rev.as_str()) {
        if i != j {
          result.push(vec![i as i32, j as i32]);
        }
      }
      
      // Check for prefix and suffix palindromes
      for k in 1..word.len() {
        // Check if prefix is palindrome
        if is_palindrome(&word_bytes[..k]) {
          let right_rev: String = word[k..].chars().rev().collect();
          if let Some(&j) = word_map.get(right_rev.as_str()) {
            if j != i {
              result.push(vec![j as i32, i as i32]);
            }
          }
        }
        
        // Check if suffix is palindrome
        if is_palindrome(&word_bytes[k..]) {
          let left_rev: String = word[..k].chars().rev().collect();
          if let Some(&j) = word_map.get(left_rev.as_str()) {
            if j != i {
              result.push(vec![i as i32, j as i32]);
            }
          }
        }
      }
      
      // Check for empty string
      if is_palindrome(word_bytes) {
        if let Some(&j) = word_map.get("") {
          if i != j {
            result.push(vec![i as i32, j as i32]);
            result.push(vec![j as i32, i as i32]);
          }
        }
      }
    }
    
    result
  }
}