LeetCode算法题-Longest Word in Dict

这是悦乐书的第303次更新，第322篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第171题（顺位题号是720）。给出表示英语词典的字符串单词数组，找到单词中长度最长的单词，此单词可以通过数组中的其他单词一次次构建一个字符而得来。如果有多个可能的答案，则返回字典顺序最小的最长单词。如果没有答案，则返回空字符串。例如：

输入：words = [“w”，“wo”，“wor”，“worl”，“world”]

输出：“world”

说明：“world”这个词可以通过“w”，“wo”，“wor”和“worl”一次构建一个字符。


输入：words = [“a”，“banana”，“app”，“appl”，“ap”，“apply”，“apple”]

输出：“apple”

说明：“apply”和“apple”都可以从字典中的其他单词构建。但是，“apple”在词典上比“apply”更小（靠前）。


注意：

• 输入中的所有字符串仅包含小写字母。

• 单词的长度将在[1,1000]范围内。

• 单词[i]的长度将在[1,30]的范围内。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

在解题前，需要先注意题目中的几个信息，一是满足题目条件的结果字符串，是有一个个字符累加起来的，在我的一次提交中，有{"ew","ewq","ewqz"}这三个字符串，我的算法算出来是第三个"ewqz"，但其实它还缺少一个"e"，是不符合题目要求的。二是如果满足题目条件的字符串有两个或者多个，需要去比较谁更小，也就是按照字母顺序由小到大排列的，谁更靠前谁更小。

思路是先将字符串放进HashMap中,key为每一个单词，value为单词的长度。循环单词数组，比较谁的长度更小，此处分为两种情况处理：一是大于已有最大长度，二是等于已有最大长度，另外，无论遇到那种情况，都需要去判断当前字符是否是由单个单词一次次累加变成的，对此单独写了一个方法判断当前单词是否符合题目要求的方法isExists。针对第二种情况，需要去比较两个单词的大小，也写了一个额外的方法isMin来判断，如果满足，就将结果字符串更新，最长长度保持不变。

Map<String, Integer> map = new HashMap<String, Integer>();
public String longestWord(String[] words) {
    for (String str : words) {
        map.put(str, str.length());
    }
    int len = Integer.MIN_VALUE;
    String result = "";
    for (String str : words) {
        if (isExists(str) && str.length() > len) {
            result = str;
            len = str.length();
        } else if (isExists(str) && str.length() == len) {
            if (result != "") {
                if (isMin(str, result)) {
                    result = str;
                }
            }
        }
    }
    return result;
}

/**
 * 判断str是否小于str2
 * @param str 新遇到的等长字符串
 * @param str2 上一次的最长字符串
 * @return true:str中的字符小于str2
 */
public boolean isMin(String str, String str2){
    for (int i=0; i<str.length(); i++) {
        if (str.charAt(i) < str2.charAt(i)) {
            return true;
        } else if (str.charAt(i) == str2.charAt(i)) {
            continue;
        } else {
            return false;
        }
    }
    return false;
}

/**
 * 判断当前字符串在数组中是否是一个个字符慢慢累加起来的
 * @param str
 * @return
 */
public boolean isExists(String str) {
    String ss = "";
    for (char ch : str.toCharArray()) {
        ss += ch;
        if (!map.containsKey(ss)) {
            return false;
        }
    }
    return true;
}

03 第二种解法

在第一种解法中，并没有用到HashMap中的value值，因此可以使用HashSet来存储数组中的单词。其次，也可以通过数组排序的方式，省去后续循环中判断最长长度相等的情况，也省去了比较两个字符串谁更小的判断，更加的简洁。

Set<String> set = new HashSet<String>();
public String longestWord2(String[] words) {
    Arrays.sort(words);
    for (String word : words) {
        set.add(word);
    }
    int len = Integer.MIN_VALUE;
    String result = "";
    for (String str : words) {
        if (isExists2(str) && str.length() > len) {
            result = str;
            len = str.length();
        }
    }
    return result;
}

public boolean isExists2(String str) {
    String ss = "";
    for (char ch : str.toCharArray()) {
        ss += ch;
        if (!set.contains(ss)) {
            return false;
        }
    }
    return true;
}

04 第三种解法

也可以只使用一个循环来解决。依旧是数组排序，使用HashSet存储数组中的单词，但是存入HashSet的操作是在循环中进行的，如果当前单词的长度等于1或者其本身的子串也存在于HashSet中，才存入HashSet，此步骤就相当于第一种解法和第二种解法中判断当前单词是否符合题目要求，由一个字符一次次累加得来的。如果当前字符的长度大于结果单词的长度，就进行赋值更新操作。

public String longestWord3(String[] words) {
    Set<String> set = new HashSet<String>();
    Arrays.sort(words);
    String result = "";
    for (String word : words) {
        if (word.length() == 1 || set.contains(word.substring(0, word.length()-1))) {
            if (word.length() > result.length()) {
                result = word;
            }
            set.add(word);
        }
    }
    return result;
}

05 第四种解法

我们也可以不借助排序来实现，其实也是对第二种解法的优化。依旧是使用HashSet，也借助了一个辅助方法isExists2来判断当前单词是否符合题目要求，但不同的是，在循环中，此判断只在当前单词长度大于结果单词的长度，或者两者长度相等且新单词小于结果单词这两种情况下进行，而不像第二种解法那样，每次都去先判断当前单词是否符合题目要求，再去比较长度。其中，比较两个单词的大小借助了字符串自带的compareTo方法。

Set<String> set = new HashSet<String>();
public String longestWord4(String[] words) {
    for (String word : words) {
        set.add(word);
    }
    String result = "";
    for (String word : words) {
        if (word.length() > result.length() || (word.length() == result.length() && word.compareTo(result) < 0)) {
            if (isExists2(word)) {
                result = word;
            }
        }
    }
    return result;
}

public boolean isExists2(String str) {
    String ss = "";
    for (char ch : str.toCharArray()) {
        ss += ch;
        if (!set.contains(ss)) {
            return false;
        }
    }
    return true;
}

06 小结

算法专题目前已日更超过五个月，算法题文章171+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！