Question

524. Longest Word in Dictionary through Deleting

中文文档

Description

Given a string s and a string array dictionary, return _the longest string in the dictionary that can be formed by deleting some of the given string characters_. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

 

Example 1:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

Example 2:

Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"

 

Constraints:

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s and dictionary[i] consist of lowercase English letters.

Solutions

Solution 1

class Solution:
  def findLongestWord(self, s: str, dictionary: List[str]) -> str:
    def check(a, b):
      m, n = len(a), len(b)
      i = j = 0
      while i < m and j < n:
        if a[i] == b[j]:
          j += 1
        i += 1
      return j == n

    ans = ''
    for a in dictionary:
      if check(s, a) and (len(ans) < len(a) or (len(ans) == len(a) and ans > a)):
        ans = a
    return ans

class Solution {
  public String findLongestWord(String s, List<String> dictionary) {
    String ans = "";
    for (String a : dictionary) {
      if (check(s, a)
        && (ans.length() < a.length()
          || (ans.length() == a.length() && a.compareTo(ans) < 0))) {
        ans = a;
      }
    }
    return ans;
  }

  private boolean check(String a, String b) {
    int m = a.length(), n = b.length();
    int i = 0, j = 0;
    while (i < m && j < n) {
      if (a.charAt(i) == b.charAt(j)) {
        ++j;
      }
      ++i;
    }
    return j == n;
  }
}

class Solution {
public:
  string findLongestWord(string s, vector<string>& dictionary) {
    string ans = "";
    for (string& a : dictionary)
      if (check(s, a) && (ans.size() < a.size() || (ans.size() == a.size() && a < ans)))
        ans = a;
    return ans;
  }

  bool check(string& a, string& b) {
    int m = a.size(), n = b.size();
    int i = 0, j = 0;
    while (i < m && j < n) {
      if (a[i] == b[j]) ++j;
      ++i;
    }
    return j == n;
  }
};

func findLongestWord(s string, dictionary []string) string {
  ans := ""
  check := func(a, b string) bool {
    m, n := len(a), len(b)
    i, j := 0, 0
    for i < m && j < n {
      if a[i] == b[j] {
        j++
      }
      i++
    }
    return j == n
  }
  for _, a := range dictionary {
    if check(s, a) && (len(ans) < len(a) || (len(ans) == len(a) && a < ans)) {
      ans = a
    }
  }
  return ans
}

function findLongestWord(s: string, dictionary: string[]): string {
  dictionary.sort((a, b) => {
    if (a.length === b.length) {
      return b < a ? 1 : -1;
    }
    return b.length - a.length;
  });
  const n = s.length;
  for (const target of dictionary) {
    const m = target.length;
    if (m > n) {
      continue;
    }
    let i = 0;
    let j = 0;
    while (i < n && j < m) {
      if (s[i] === target[j]) {
        j++;
      }
      i++;
    }
    if (j === m) {
      return target;
    }
  }
  return '';
}

impl Solution {
  pub fn find_longest_word(s: String, mut dictionary: Vec<String>) -> String {
    dictionary.sort_unstable_by(|a, b| (b.len(), a).cmp(&(a.len(), b)));
    for target in dictionary {
      let target: Vec<char> = target.chars().collect();
      let n = target.len();
      let mut i = 0;
      for c in s.chars() {
        if i == n {
          break;
        }
        if c == target[i] {
          i += 1;
        }
      }
      if i == n {
        return target.iter().collect();
      }
    }
    String::new()
  }
}