leetcode-problem-14-longest-common-prefix.py

"""LeetCode Problem 14 - Longest Common Prefix"""

from typing import List, Optional, Text

from absl import app
from absl import flags
from absl import logging
from absl.testing import absltest

def inputs_are_valid(strings: List[Text]) -> bool:
  # There are at least 1 and at most 200 strings in the input list.
  if len(strings) < 1 or len(strings) > 200:
    return False

    for _ in strings:
      # Each string is 0-200 characters in length.
      if len(_) > 200:
        return False

      # Only lowercase characters.
      for character in _:
        if character not in 'abcdefghijklmnopqrstuvwxyz':
          return False
  return True


class TrieNode:
  def __init__(self) -> None:
    self.children = {}

  def __contains__(self, word: Text) -> bool:
    if word == '':
      return '*' in self.children
    if word[0] not in self.children:
      return False
    return word[1:] in self.children[word[0]]

  def __repr__(self) -> Text:
    return f'{self.children}'

  def add_word(self, word: Text) -> None:
    if word == '':
      self.children['*'] = TrieNode()
      return
    elif word[0] not in self.children:
      self.children[word[0]] = TrieNode()
    self.children[word[0]].add_word(word[1:])

  def longest_common_prefix(self) -> Optional[Text]:
    if len(self.children) != 1:
      return ''
    for child in self.children:
      if child == '*':
        return ''
      return child + self.children[child].longest_common_prefix()


class Trie:
  def __init__(self, words: Optional[List[Text]] = None) -> None:
    self.head = TrieNode()
    if words:
      self.add_words(words)

  def __contains__(self, word: Text) -> bool:
    return word in self.head

  def add_word(self, word: Text) -> None:
    self.head.add_word(word)

  def add_words(self, words: List[Text]) -> None:
    for word in words:
      self.add_word(word)

  def longest_common_prefix(self) -> Text:
    longest_prefix = self.head.longest_common_prefix()
    return longest_prefix if longest_prefix else ''


def create_trie_from_word_list(words: List[Text]) -> Trie:
  return Trie(words)


def longest_common_prefix(strings: List[Text]) -> Text:
  assert inputs_are_valid(strings)
  trie = create_trie_from_word_list(strings)
  return trie.longest_common_prefix()


class Solution:
  def longestCommonPrefix(self, strs: List[str]) -> str:
    return longest_common_prefix(strs)


class TestTrieNode(absltest.TestCase):
  def test_add_word(self) -> None:
    with self.subTest():
      trie_node = TrieNode()
      trie_node.add_word('tree')
      self.assertTrue('tree' in trie_node)


class TestTrie(absltest.TestCase):
  def test_add_word(self) -> None:
    trie = Trie()
    trie.add_word('cat')
    self.assertTrue('cat' in trie)


class TestSolution(absltest.TestCase):
  def test_example_cases(self) -> None:
    with self.subTest(name='Example 1'):
      strings = ['flower', 'flow', 'flight']
      actual = longest_common_prefix(strings)
      expected = 'fl'
      self.assertEqual(actual, expected)
      
    with self.subTest(name='Example 2'):
      strings = ['dog', 'racecar', 'car']
      actual = longest_common_prefix(strings)
      expected = ''
      self.assertEqual(actual, expected)

  def test_edge_cases(self) -> None:
    with self.subTest():
      strings = ['']
      actual = longest_common_prefix(strings)
      expected = ''
      self.assertEqual(actual, expected)


if __name__ == '__main__':
  absltest.main()