You are given two arrays with positive integers arr1 and arr2.
A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not.
A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have a common prefix 565 while 1223 and 43456 do not have a common prefix.
You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.
Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.
Example 1:
Input: arr1 = [1,10,100], arr2 = [1000] Output: 3 Explanation: There are 3 pairs (arr1[i], arr2[j]): - The longest common prefix of (1, 1000) is 1. - The longest common prefix of (10, 1000) is 10. - The longest common prefix of (100, 1000) is 100. The longest common prefix is 100 with a length of 3.
Example 2:
Input: arr1 = [1,2,3], arr2 = [4,4,4] Output: 0 Explanation: There exists no common prefix for any pair (arr1[i], arr2[j]), hence we return 0. Note that common prefixes between elements of the same array do not count.
Constraints:
1 <= arr1.length, arr2.length <= 5 * 10<sup>4</sup>1 <= arr1[i], arr2[i] <= 10<sup>8</sup>class Trie
{
public:
unordered_map<char, Trie *> children;
bool flag;
Trie()
{
flag = false;
}
};
class Solution
{
public:
Trie *root;
Solution()
{
root = new Trie();
}
void insert(string s)
{
Trie *node = root;
for (auto c : s)
{
if (node->children.find(c) == node->children.end())
{
node->children[c] = new Trie;
}
node = node->children[c];
}
node->flag = true;
}
bool search(string s)
{
Trie *node = root;
for (auto c : s)
{
if (node->children.find(c) == node->children.end())
{
return false;
}
node = node->children[c];
}
return node->flag;
}
bool pfxSearch(string s)
{
Trie *node = root;
for (auto c : s)
{
if (node->children.find(c) == node->children.end())
{
return false;
}
node = node->children[c];
}
return true;
}
int longestCommonPrefix(vector<int> &a1, vector<int> &a2)
{
// Trie* node=root;
// int ans = 0;
// for (int i = 0; i < a1.size(); i++)
// {
// for (int j = 0; j < a2.size(); j++)
// {
// string x = to_string(a1[i]);
// string y = to_string(a2[j]);
// int len = 0;
// for (int k = 0; k < x.size(); k++)
// {
// if (x[k] == y[k])
// {
// len++;
// }
// else
// break;
// }
// ans = max(len, ans);
// }
// }
// return ans;
for(int i=0;i<a1.size();i++){
insert(to_string(a1[i]));
}
int ans=0;
for(int i=0;i<a2.size();i++){
string s=to_string(a2[i]);
Trie *node = root;
int len=0;
for(auto c:s){
if(node->children.find(c)==node->children.end()) break;
node=node->children[c];
len++;
}
ans=max(len,ans);
}
return ans;
}
};
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:
wordsQuery[0] = "cd", strings from wordsContainer that 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.wordsQuery[1] = "bcd", strings from wordsContainer that 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.wordsQuery[2] = "xyz", there is no string from wordsContainer that 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:
wordsQuery[0] = "gh", strings from wordsContainer that 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.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.wordsQuery[2] = "acbfegh", strings from wordsContainer that 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 <= 10<sup>4</sup>1 <= wordsContainer[i].length <= 5 * 10<sup>3</sup>1 <= wordsQuery[i].length <= 5 * 10<sup>3</sup>wordsContainer[i] consists only of lowercase English letters.wordsQuery[i] consists only of lowercase English letters.wordsContainer[i].length is at most 5 * 10<sup>5</sup>.wordsQuery[i].length is at most 5 * 10<sup>5</sup>.class Trie
{
public:
map<char, Trie *> children;
bool flag;
int index;
int len;
Trie()
{
flag = false;
index = -1;
len=1e9;
}
};
class Solution
{
public:
Trie *root;
Solution()
{
root = new Trie();
}
vector<int> stringIndices(vector<string> &wC, vector<string> &wQ)
{
int minLength=1e9,minIndex=-1;
for (int i = 0; i < wC.size(); i++)
{
Trie *node = root;
string rW = wC[i];
reverse(rW.begin(), rW.end());
int sz=rW.size();
for(auto c:rW){
if(node->children.find(c)==node->children.end()){
node->children[c]=new Trie();
}
node= node->children[c];
if(node->len> sz){
node->len=sz;
node->index=i;
}
}
if(minLength>sz){
minLength=sz;
minIndex=i;
}
}
vector<int> ans;
for(int i=0;i<wQ.size();i++){
Trie *node = root;
string rQ=wQ[i];
reverse(rQ.begin(), rQ.end());
int l=-1;
for(auto c:rQ){
if(node->children.find(c)==node->children.end()){
l=node->index;
break;
}
node=node->children[c];
}
l=node->index;
if(l==-1){
l=minIndex;
}
ans.push_back(l);
}
return ans;
}
};
You are given an array words of size n consisting of non-empty strings.
We define the score of a string term as the number of strings words[i] such that term is a prefix of words[i].
words = ["a", "ab", "abc", "cab"], then the score of "ab" is 2, since "ab" is a prefix of both "ab" and "abc".Return _an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of _words[i].
Note that a string is considered as a prefix of itself.
Example 1:
Input: words = ["abc","ab","bc","b"] Output: [5,4,3,2] Explanation: The answer for each string is the following: - "abc" has 3 prefixes: "a", "ab", and "abc". - There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc". The total is answer[0] = 2 + 2 + 1 = 5. - "ab" has 2 prefixes: "a" and "ab". - There are 2 strings with the prefix "a", and 2 strings with the prefix "ab". The total is answer[1] = 2 + 2 = 4. - "bc" has 2 prefixes: "b" and "bc". - There are 2 strings with the prefix "b", and 1 string with the prefix "bc". The total is answer[2] = 2 + 1 = 3. - "b" has 1 prefix: "b". - There are 2 strings with the prefix "b". The total is answer[3] = 2.
Example 2:
Input: words = ["abcd"] Output: [4] Explanation: "abcd" has 4 prefixes: "a", "ab", "abc", and "abcd". Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 1000words[i] consists of lowercase English letters.class Trie{
public:
unordered_map<char,Trie*>children;
int count;
Trie(){
count=0;
}
};
class Solution {
public:
Trie* root;
Solution(){
root=new Trie();
}
vector<int> sumPrefixScores(vector<string>& words) {
for(int i=0;i<words.size();i++){
Trie* node=root;
string s=words[i];
for(auto c:s){
if(node->children.find(c)==node->children.end()){
node->children[c]=new Trie();
}
node=node->children[c];
node->count=node->count+1;
}
}
vector<int> ans;
for(int i=0;i<words.size();i++){
Trie* node=root;
int sum=0;
string s=words[i];
for(auto c:s){
node=node->children[c];
sum+=node->count;
}
ans.push_back(sum);
node=root;
}
return ans;
}
};