Semordnilap

Tags

Semordnilap

Category

Strings

Difficulty

Easy

Problem Statement

Given a list of unique strings, find all pairs of words where one word is the reverse of the other. Each pair should be returned exactly once. A word is not considered a semordnilap of itself (unless it appears twice, but the input contains unique strings).

Intuition

The word "semordnilap" is "palindromes" spelled backward. Two words form a semordnilap pair if one is the exact reverse of the other. By storing all words in a set, we can check for each word whether its reverse also exists in the set. To avoid counting each pair twice, we remove or mark words as we find their matches.

Approach

  1. Insert all words into a set for O(1) lookup.
  2. Initialize an empty result list.
  3. For each word in the list:
    • Compute its reverse.
    • If the reverse exists in the set and the reverse is not the word itself:
      • Add the pair [word, reverse] to the result.
      • Remove both the word and its reverse from the set to prevent duplicate pairs.
  4. Return the result.

Pseudocode

function semordnilap(words):
    wordSet = set(words)
    result = []

    for word in words:
        reversed = reverse(word)
        if reversed in wordSet and reversed != word:
            result.append([word, reversed])
            wordSet.remove(word)
            wordSet.remove(reversed)

    return result

Time & Space Complexity

  • Time: O(n * m) where n is the number of words and m is the length of the longest word. Reversing each word takes O(m) and the set lookup is O(m) for string hashing.
  • Space: O(n * m) for storing all words in the set.

Key Insights

  • Using a set provides efficient O(1) average-case lookups for reversed strings.
  • Removing both words from the set when a pair is found prevents reporting the same pair twice.
  • The check reversed != word prevents palindromes from pairing with themselves.
  • Each valid pair is found exactly once since one of the two words in the pair will be encountered first during iteration.

Edge Cases

  • Empty list: return an empty result.
  • No semordnilap pairs exist: return an empty result.
  • Palindromic words (e.g., "racecar"): these are not paired with themselves since the input has unique strings.
  • Single character words: two different single-character words cannot be reverses of each other (they would have to be the same character, but the input is unique).
  • Words of different lengths can never form a pair since reversing preserves length.

Linked mentions