最长公共后缀查询
难度:
标签:
题目描述
You are given two arrays of strings wordsContainer and wordsQuery.
For each wordsQuery[i], you need to find a string from wordsContainer that has the longest common suffix with wordsQuery[i]. If there are two or more strings in wordsContainer that share the longest common suffix, find the string that is the smallest in length. If there are two or more such strings that have the same smallest length, find the one that occurred earlier in wordsContainer.
Return an array of integers ans, where ans[i] is the index of the string in wordsContainer that has the longest common suffix with wordsQuery[i].
Example 1:
Input: wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
Output: [1,1,1]
Explanation:
Let's look at each wordsQuery[i] separately:
- For
wordsQuery[0] = "cd", strings fromwordsContainerthat share the longest common suffix"cd"are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3. - For
wordsQuery[1] = "bcd", strings fromwordsContainerthat share the longest common suffix"bcd"are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3. - For
wordsQuery[2] = "xyz", there is no string fromwordsContainerthat shares a common suffix. Hence the longest common suffix is"", that is shared with strings at index 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.
Example 2:
Input: wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
Output: [2,0,2]
Explanation:
Let's look at each wordsQuery[i] separately:
- For
wordsQuery[0] = "gh", strings fromwordsContainerthat share the longest common suffix"gh"are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6. - For
wordsQuery[1] = "acbfgh", only the string at index 0 shares the longest common suffix"fgh". Hence it is the answer, even though the string at index 2 is shorter. - For
wordsQuery[2] = "acbfegh", strings fromwordsContainerthat share the longest common suffix"gh"are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6.
Constraints:
1 <= wordsContainer.length, wordsQuery.length <= 1041 <= wordsContainer[i].length <= 5 * 1031 <= wordsQuery[i].length <= 5 * 103wordsContainer[i]consists only of lowercase English letters.wordsQuery[i]consists only of lowercase English letters.- Sum of
wordsContainer[i].lengthis at most5 * 105. - Sum of
wordsQuery[i].lengthis at most5 * 105.
代码结果
运行时间: 179 ms, 内存: 28.7 MB
/*
* 题目思路：
* 对于每个wordsQuery[i]，需要找到wordsContainer中与其有最长公共后缀的字符串。
* 如果有多个字符串有相同长度的最长公共后缀，则选择长度最短的字符串。
* 如果仍有多个字符串满足条件，则选择wordsContainer中最早出现的字符串。
*/
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public int[] findLongestCommonSuffix(String[] wordsContainer, String[] wordsQuery) {
return Arrays.stream(wordsQuery)
.mapToInt(query -> {
return IntStream.range(0, wordsContainer.length)
.boxed()
.max(Comparator.comparingInt((Integer index) -> getCommonSuffixLength(wordsContainer[index], query))
.thenComparingInt(index -> -wordsContainer[index].length())
.thenComparingInt(index -> -index))
.orElse(-1);
}).toArray();
}
private int getCommonSuffixLength(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
int len = 0;
while (len < len1 && len < len2 && s1.charAt(len1 - len - 1) == s2.charAt(len2 - len - 1)) {
len++;
}
return len;
}
}
解释
方法:
时间复杂度:
空间复杂度: