Implement the minimumIndexSumCommonString method that returns the common string with the smallest index sum.
The input contains two string arrays, a and b, along with their sizes. Your task is to find a common string whose index sum is minimum.
The index sum of a common string is its index in the first array plus its index in the second array.
For example, if Shogun appears at index 0 in the first array and index 1 in the second array, its index sum is 1. Return the common string with the smallest index sum. If there is no common string, return an empty string.
Example 1
[Shogun,Tapioca,Burger]3[Burger,Shogun]2ShogunExample 2
[A,B,C]3[C,A]2AExample 3
[A,B,C]3[D,E]2Store the index of each string from the first array in a map.
Then scan the second array. Whenever a string is also found in the first array, calculate the sum of both indexes. If this sum is smaller than the best sum found so far, update the answer.
After checking all strings, return the best common string. If no common string was found, return an empty string.
Pseudocode:
function minimumIndexSumCommonString(a, sizeA, b, sizeB):
create empty map indexA
for i from 0 to sizeA - 1:
indexA[a[i]] = i
bestSum = very large number
answer = empty string
for j from 0 to sizeB - 1:
if b[j] exists in indexA:
sum = indexA[b[j]] + j
if sum < bestSum:
bestSum = sum
answer = b[j]
return answer