12
(I'm writing this in the context of JavaScript, but will accept an algorithmically correct answer in any language)
How do you find the shortest substring of each element in an array of strings where the substring is NOT contained within any of the other elements, ignoring case?
Suppose I have an input array such as:
var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
The output should be something like:
var uniqueNames = ["ne", "h", "ua", "ka", "i", "r"];
For my purposes, you can safely assume that no element will be wholly contained within another element.
My Thoughts:
It seems that one could probably brute force this, along the lines of:
var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
var uniqueNames = [], nameInd, windowSize, substrInd, substr, otherNameInd, foundMatch;
// For each name
for (nameInd = 0; nameInd < names.length; nameInd++)
{
var name = names[nameInd];
// For each possible substring length
windowLoop:
for (windowSize = 1; windowSize <= name.length; windowSize++)
{
// For each starting index of a substring
for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++)
{
substr = name.substring(substrInd,substrInd+windowSize).toLowerCase();
foundMatch = false;
// For each other name
for (otherNameInd = 0; otherNameInd < names.length; otherNameInd++)
{
if (nameInd != otherNameInd && names[otherNameInd].toLowerCase().indexOf(substr) > -1)
{
foundMatch = true;
break;
}
}
if (!foundMatch)
{
//