题解 | #牛族寻找祖先#
牛族寻找祖先
https://www.nowcoder.com/practice/eea77a55616f4961801796c7d36369db
考察的知识点:字符串;
解答方法分析:
- 判断输入的字符串数组是否为空,如果为空则返回空字符串""。
- 初始化最长公共前缀为第一个字符串names[0],长度为prefixLen。
- 遍历数组中的每个字符串,从第二个字符串开始。
- 在遍历每个字符串时,不断与当前的最长公共前缀进行匹配,如果匹配到最后一位或者当前字符与最长公共前缀的对应位置不相同,则最长公共前缀更新为当前匹配的前缀。
- 遍历完成后,返回最长公共前缀。
所用编程语言:C++;
完整编程代码:↓
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param names string字符串vector * @return string字符串 */ string findAncestor(vector<string>& names) { if (names.empty()) { return ""; } string prefix = names[0]; int prefixLen = prefix.length(); for (int i = 1; i < names.size(); i++) { string curr = names[i]; int currLen = curr.length(); int j = 0; while (j < prefixLen && j < currLen && prefix[j] == curr[j]) { j++; } prefix = prefix.substr(0, j); prefixLen = j; if (prefixLen == 0) { return ""; } } return prefix; } };