题目描述与示例

题目描述

小王在进行游戏大闯关，有一个关卡需要输入一个密码才能通过，密码获得的条件如下：在一个密码本中，每一页都有一个由 26 个小写字母组成的若干位密码，从它的末尾开始依次去掉一位得到的新密码也在密码本中存在。请输出符合要求的最长密码，如果由多个符合要求的密码，则返回字典序最大的密码。若没有符合要求的密码，则返回空字符串。

输入

密码本由一个字符串数组组成，不同元素之间使用空格隔开，每一个元素代表密码本每一页的密码。

输出

一个字符串

示例一

输入

h he hel hell hello

输出

hello

说明

"hello" 从末尾依次去掉一位得到的 "hell", "hel", "he", "h"在密码本中都存在。

示例二

输入

b eredderd bw bww bwwl bwwlm bwwln

输出

bwwln

解题思路

最朴素的解法是将所有字符串都存在一个哈希表password_set中，然后遍历字符串数组中的每一个密码password，对每一个password都去判断其所有的前缀是否也位于password_set中。如果满足，则把password和ans比较并且更新ans。

这种做法虽然思路直接简单，但略显笨重，会出现很多重复计算。

以示例一为例子：

对于单词hell，需要分别考虑前缀h、he、hel
对于单词hello，需要分别考虑前缀h、he、hel、hell
前缀h、he、hel对于单词hello而言，显然是重复计算了。
假设我们已经知道单词hell是一个有效的密码，那么对于单词hello，我们就只需要去考虑hell这个前缀，而不需要再去考虑h、he、hel这三个前缀了。
换句话说，单词hello是否是一个有效的密码，可以由其去掉末尾的前缀hell是否是一个有效的密码来决定。这本质上是一种动态规划的思想。（动态规划更详细的内容在后面会讲到）

如果用动态规划的语言来描述，即：password是一个有效密码，****当且仅当password[:-1]是一个有效密码。

那么现在问题就变成了：如何能够在判断password是一个有效密码之前，就先判断得到password[:-1]是否有效？这个问题就很简单了。我们只需要对原来的字符串数组password_lst按照字典序进行排序，就可以保证在password进行判断时，password[:-1]已经被判断过了。

我们可以构建一个用于储存所有有效密码的哈希集合valid_set。然后遍历排序过的字符串数组password_lst中的每一个密码password，如果其去掉末尾的前缀password[:-1]位于valid_set中，说明password也是一个有效密码，需要将其加入valid_set中，同时更新ans。

for password in password_lst:
    if password[:-1] in valid_set:
        valid_set.add(password)
        ans = password

注意valid_set初始化时要包含一个空串""，因为只有一个字符的密码比如"h"，去掉最末尾的字符之后是一个空串""，"h"理应是一个有效的密码，故""应该存在于valid_set中。即：

valid_set = {""}

代码

解法一

（哈希集合暴力解法，只能通过部分用例）

Python

# 题目：2023Q1A-寻找密码
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：哈希表暴力解法
# 代码看不懂的地方，请直接在群上提问

# 将输入字符串分割为字符串数组，并且存入哈希集合中
password_lst = list(input().split())
password_set = set(password_lst)
# 初始化答案为一个空字符串
ans = str()

# 遍历password_lst中的所有密码单词password
for password in password_lst:
    # 如果password的长度比ans小，不可能是答案，直接跳过
    if len(password) < len(ans):
        continue
    # password有可能不符合要求，设置一个标记isValid，初始化为True表示该密码符合要求
    isValid = True
    # 遍历password的所有前缀password[:i]，判断前缀是否均位于password_set中
    for i in range(1, len(password)):
        # 若某一个前缀不位于哈希集合password_set中，则该password无效，修改isValid为False，且退出循环
        if password[:i] not in password_set:
            isValid = False
            break
    # isValid为True，说明该password有效，将其与ans比较并更新ans
    if isValid:
        if len(password) > len(ans):
            ans = password
        else:
            ans = max(ans, password)
print(ans)

Java

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] passwordArray = scanner.nextLine().split(" ");

        HashSet<String> passwordSet = new HashSet<>();
        for (String password : passwordArray) {
            passwordSet.add(password);
        }

        String ans = "";

        for (String password : passwordArray) {
            if (password.length() < ans.length()) {
                continue;
            }

            boolean isValid = true;
            for (int i = 1; i < password.length(); i++) {
                if (!passwordSet.contains(password.substring(0, i))) {
                    isValid = false;
                    break;
                }
            }

            if (isValid) {
                if (password.length() > ans.length()) {
                    ans = password;
                } else {
                    ans = ans.compareTo(password) < 0 ? password : ans;
                }
            }
        }

        System.out.println(ans);
    }
}

C++

“`C++
#include
#include
#include
#include
#include

int main() {
std::string line;
std::getline(std::cin, line);
std::istringstream iss(line);

std::vector<std::string> password_lst;
std::unordered_set<std::string> password_set;

std::string password;
while (iss >> password) {
    password_lst.push_back(password);
    password_set.insert(password);
}

std::string ans;

for (const std::string& password : password_lst) {
    if (password.length() < ans.length()) {
        continue;
    }

    bool isValid = true;
    for (int i = 1; i < password.length(); i++) {
        if (password_set.find(password.substr(0, i)) == password_set.end()) {
            isValid = false;
            break;
        }
    }

    if (isValid) {
        if (password.length() > ans.length()) {
            ans = password;
        } else {
            ans = std::max(ans, password);
        }
    }
}

std::cout << ans << std::endl;

return 0;

}

### 时空复杂度

时间复杂度：`O(NM)`。遍历每个单词、每个字符所需的时间。

空间复杂度：`O(NM)`。

`N`为单词数目，`M`为单词平均长度。

## 解法二

（哈希集合优化解法，含DP思想，可以通过全部用例）

### Python

```Python
# 题目：2023Q1A-寻找密码
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：哈希表优化解法
# 代码看不懂的地方，请直接在群上提问


password_lst = input().split()
# 对输入的字符串数组进行升序排序
password_lst.sort()

# 初始化一个表示有效密码的哈希集合，初始化其中仅包含空字符串
valid_set = {""}
# 初始化答案为空字符串
ans = ""

# 从头到尾遍历升序字符串数组password_lst中的密码password
for password in password_lst:
    # 如果password去掉最后一位的结果password[:-1]，位于valid_set哈希集合中
    # 说明当前的password是一个有效密码，将其加入valid_set，同时更新ans
    if password[:-1] in valid_set:
        valid_set.add(password)
        if len(password) >= len(ans):
            ans = password

print(ans)
</code></pre>

<h3>Java</h3>

<pre><code class="language-Java ">import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] passwordArray = scanner.nextLine().split(" ");

        Arrays.sort(passwordArray);

        HashSet<String> validSet = new HashSet<>();
        validSet.add("");

        String ans = "";

        for (String password : passwordArray) {
            if (password.substring(0, password.length() - 1).equals("") || validSet.contains(password.substring(0, password.length() - 1))) {
                validSet.add(password);
                if (password.length() >= ans.length()) {
                    ans = password;
                }
            }
        }

        System.out.println(ans);
    }
}
</code></pre>

<h3>C++</h3>


```C++
#include 
#include 
#include 
#include 
#include 


int main() {
    std::string line;
    std::getline(std::cin, line);
    std::istringstream iss(line);

std::vector<std::string> password_lst;
std::string password;
while (iss >> password) {
    password_lst.push_back(password);
}

std::sort(password_lst.begin(), password_lst.end());

std::unordered_set<std::string> valid_set;
valid_set.insert("");

std::string ans;

for (const std::string& password : password_lst) {
    if (password.substr(0, password.length() - 1) == "" || valid_set.find(password.substr(0, password.length() - 1)) != valid_set.end()) {
        valid_set.insert(password);
        if (password.length() >= ans.length()) {
            ans = password;
        }
    }
}

std::cout << ans << std::endl;

return 0;

}
### 时空复杂度

时间复杂度：`O(NlogN)`。排序所需的时间复杂度。

空间复杂度：`O(NM)`。哈希集合所占的额外空间。

`N`为单词数目，`M`为单词平均长度。

## 解法三*

（前缀树解法，不要求掌握，感兴趣的同学可以研究一下）

### Python

```Python
# 题目：2023Q1A-寻找密码
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：前缀树
# 代码看不懂的地方，请直接在群上提问

# 前缀树的节点类
class Trie():
    def __init__(self) -> None:
        self.children = [None] * 26
        self.isEnd = False

    # 将单词word加入前缀树的函数
    def addword(self, word):
        node = self
        for ch in word:
            ch_idx = ord(ch) - 97  # ASCII to idx
            # 以下两行用来通过最后一个用例..输入了非小写字母的字符串
            if ch_idx > 25 or ch_idx < 0:
                return
            if node.children[ch_idx] is None:
                node.children[ch_idx] = Trie()
            node = node.children[ch_idx]
        node.isEnd = True

    # 检查word的所有前缀是否存在的函数
    def checkPrefix(self, word):
        node = self
        for ch in word:
            ch_idx = ord(ch) - 97
            if node.children[ch_idx].isEnd == False:
                return False
            node = node.children[ch_idx]
        return True


if __name__ == "__main__":
    lst = input().split()
    ans = ""

    root = Trie()
    for word in lst:  # 构建前缀树
        root.addword(word)

    for word in lst:
        if len(word) < len(ans):
            continue
        if root.checkPrefix(word):
            if len(word) > len(ans):
                ans = word
            else:
                ans = max(ans, word)
    print(ans)
</code></pre>

<h3>Java</h3>

<pre><code class="language-Java ">import java.util.Scanner;

class Main {
    static class Trie {
        Trie[] children;
        boolean isEnd;

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        public void addWord(String word) {
            Trie node = this;
            for (char ch : word.toCharArray()) {
                int chIdx = ch - 'a';
                if (chIdx < 0 || chIdx >= 26) {
                    return;
                }
                if (node.children[chIdx] == null) {
                    node.children[chIdx] = new Trie();
                }
                node = node.children[chIdx];
            }
            node.isEnd = true;
        }

        public boolean checkPrefix(String word) {
            Trie node = this;
            for (char ch : word.toCharArray()) {
                int chIdx = ch - 'a';
                if (!node.children[chIdx].isEnd) {
                    return false;
                }
                node = node.children[chIdx];
            }
            return true;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] lst = scanner.nextLine().split(" ");
        String ans = "";

        Trie root = new Trie();
        for (String word : lst) {
            root.addWord(word);
        }

        for (String word : lst) {
            if (word.length() < ans.length()) {
                continue;
            }
            if (root.checkPrefix(word)) {
                if (word.length() > ans.length()){
                    ans = word;
                }
                else{
                    ans = (ans.compareTo(word) > 0) ? ans : word;
                }
            }
        }

        System.out.println(ans);
    }
}
</code></pre>

<h3>C++</h3>


```C++
#include 
#include 


using namespace std;

class Trie {
public:
    Trie* children[26];
    bool isEnd;

Trie() {
    for (int i = 0; i < 26; ++i) {
        children[i] = nullptr;
    }
    isEnd = false;
}

void addWord(string word) {
    Trie* node = this;
    for (char ch : word) {
        int chIdx = ch - 'a';
        if (chIdx < 0 || chIdx >= 26) {
            return;
        }
        if (node->children[chIdx] == nullptr) {
            node->children[chIdx] = new Trie();
        }
        node = node->children[chIdx];
    }
    node->isEnd = true;
}

bool checkPrefix(string word) {
    Trie* node = this;
    for (char ch : word) {
        int chIdx = ch - 'a';
        if (!node->children[chIdx]->isEnd) {
            return false;
        }
        node = node->children[chIdx];
    }
    return true;
}

};
int main() {

    vector lst;

    string input;

    getline(cin, input);

    size_t startPos = 0;

    size_t endPos = input.find(' ');

    while (endPos != string::npos) {

        lst.push_back(input.substr(startPos, endPos - startPos));

        startPos = endPos + 1;

        endPos = input.find(' ', startPos);

    }

    lst.push_back(input.substr(startPos));
string ans = "";

Trie* root = new Trie();
for (string word : lst) {
    root->addWord(word);
}

for (string word : lst) {
    if (word.length() < ans.length()) {
        continue;
    }
    if (root->checkPrefix(word)) {
        if (word.length() > ans.length()){
            ans = word;
        }
        else{
            ans= (ans.compare(word) > 0) ? ans : word;
        }
    }
}

cout << ans << endl;

return 0;

}
```
时空复杂度
时间复杂度：O(NM)。建树、检查前缀的时间。
空间复杂度：O(D)。
N为单词数目，M为单词平均长度，D为前缀树的节点数，远小于NM。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）


	
		
            
                            
                    abc123算法训练营永久会员

题目描述与示例

题目描述

输入

输出

示例一

输入

输出

说明

示例二

输入

输出

解题思路

代码

解法一

Python

Java

C++

时空复杂度

说明

相关文章