Question

面试题 17.15. 最长单词

English Version

题目描述

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

示例：

输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
输出： "dogwalker"
解释： "dogwalker"可由"dog"和"walker"组成。

提示：

• 0 <= len(words) <= 100
• 1 <= len(words[i]) <= 100

解法

方法一：前缀树 + DFS

class Trie:
  def __init__(self):
    self.children = [None] * 26
    self.is_end = False

  def insert(self, word):
    node = self
    for c in word:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        node.children[idx] = Trie()
      node = node.children[idx]
    node.is_end = True

  def search(self, word):
    node = self
    for c in word:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        return False
      node = node.children[idx]
    return node.is_end


class Solution:
  def longestWord(self, words: List[str]) -> str:
    def cmp(a, b):
      if len(a) != len(b):
        return len(a) - len(b)
      return -1 if a > b else 1

    def dfs(w):
      return not w or any(
        trie.search(w[:i]) and dfs(w[i:]) for i in range(1, len(w) + 1)
      )

    words.sort(key=cmp_to_key(cmp))
    trie = Trie()
    ans = ""
    for w in words:
      if dfs(w):
        ans = w
      trie.insert(w)
    return ans

class Trie {
  Trie[] children = new Trie[26];
  boolean isEnd;

  void insert(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      c -= 'a';
      if (node.children[c] == null) {
        node.children[c] = new Trie();
      }
      node = node.children[c];
    }
    node.isEnd = true;
  }

  boolean search(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      c -= 'a';
      if (node.children[c] == null) {
        return false;
      }
      node = node.children[c];
    }
    return node.isEnd;
  }
}

class Solution {
  private Trie trie = new Trie();

  public String longestWord(String[] words) {
    Arrays.sort(words, (a, b) -> {
      if (a.length() != b.length()) {
        return a.length() - b.length();
      }
      return b.compareTo(a);
    });
    String ans = "";
    for (String w : words) {
      if (dfs(w)) {
        ans = w;
      }
      trie.insert(w);
    }
    return ans;
  }

  private boolean dfs(String w) {
    if ("".equals(w)) {
      return true;
    }
    for (int i = 1; i <= w.length(); ++i) {
      if (trie.search(w.substring(0, i)) && dfs(w.substring(i))) {
        return true;
      }
    }
    return false;
  }
}

type Trie struct {
  children [26]*Trie
  isEnd  bool
}

func newTrie() *Trie {
  return &Trie{}
}
func (this *Trie) insert(word string) {
  node := this
  for _, c := range word {
    c -= 'a'
    if node.children[c] == nil {
      node.children[c] = newTrie()
    }
    node = node.children[c]
  }
  node.isEnd = true
}

func (this *Trie) search(word string) bool {
  node := this
  for _, c := range word {
    c -= 'a'
    if node.children[c] == nil {
      return false
    }
    node = node.children[c]
  }
  return node.isEnd
}

func longestWord(words []string) string {
  sort.Slice(words, func(i, j int) bool {
    a, b := words[i], words[j]
    if len(a) != len(b) {
      return len(a) < len(b)
    }
    return a > b
  })
  trie := newTrie()
  var dfs func(string) bool
  dfs = func(w string) bool {
    if len(w) == 0 {
      return true
    }
    for i := 1; i <= len(w); i++ {
      if trie.search(w[:i]) && dfs(w[i:]) {
        return true
      }
    }
    return false
  }
  ans := ""
  for _, w := range words {
    if dfs(w) {
      ans = w
    }
    trie.insert(w)
  }
  return ans
}