0
$\begingroup$

Assume I have the following list of companies:

  • Apple
  • Big Apple
  • Google

Then I have this sample string:

Big Apple is a company that is trying to be the next Google.

Given the list of companies and the sample string above, how can I find the list of companies in the sample string?

If I iterate through the list of companies and search for it in the sample string, I would find three matches: Apple (because "Apple" exist in "Big Apple"), Big Apple, and Google. In my scenario, I wouldn't want just Apple to match since Big Apple is a more accurate match.

I'm trying to implement the solution in PHP, but a general description/strategy on how to solve this would be helpful.

Improve this question
$\endgroup$
6
  • $\begingroup$ Welcome to Computer Science! The first thing we should have is a clear definition of the most accurate string for a match. How about the following criteria? Substring $S$ is said to be prefered to substring $T$ if and only $S$ is longer than $T$ or, if it is as long as $T$, it appears earlier. A substring is called matched if it matches a company name. A substring will be counted as a match if and only if it is a matched substring and no matched substring intersecting it is prefered to it. In other words, only matched and maximally prefered substrings will be counted as "most accurate strings" $\endgroup$
    – John L.
    Commented Nov 18, 2018 at 3:31
  • $\begingroup$ "or, if it is as long as T, it appears earlier" -- the reliance on sorting order could be a potential flaw? Your definition seems right, I think. How do I solve? $\endgroup$
    – StackOverflowNewbie
    Commented Nov 18, 2018 at 3:39
  • $\begingroup$ Are you really concerned about performance? If not, then you can just sort the given list of company names by length. Iterate through each position of the sample string. For each position, try matching the company names from the longest to shortest. Once matched, removed that matched substring. $\endgroup$
    – John L.
    Commented Nov 18, 2018 at 15:57
  • $\begingroup$ @JohnL. I think your definition might be a bit too 'strict' for this scenario. Consider this example: $S = abcd$ and the companies $\{abc, cd, d\}$. Your definition would only consider $\{abc\}$ in the solution, but OP would prefer $\{abc, d\}$ to be the answer, I believe. $\endgroup$
    – CodeChef
    Commented Apr 12, 2020 at 1:41
  • $\begingroup$ Instead I propose this slight variant: Substring $S$ is said to be preferred to substring $T$ if and only if $S$ is longer than $T$ or, if it is as long as $T$, it appears earlier. A substring is called matched if it matches a company name. A set of matched substrings is called a Feasible Set if every pair of substrings in it is disjoint. Now, consider any two Feasible Sets. Order each of them internally by the "preferred" total order, with the most preferred substrings at the beginning. The Feasible Set which is 'lexicographically more preferred' is the more preferred Feasible Set of the two. $\endgroup$
    – CodeChef
    Commented Apr 12, 2020 at 1:49

2 Answers 2

Reset to default
1
$\begingroup$

From your explanations I understand that "most accurate" should be understood as "longest".

  • Sort the search strings by decreasing length.

  • Perform searches of the strings in that order.

  • Every time you find a match, delete these characters from the target string.

E.g. "Big Apple", "Google", "Apple".

"Big Apple is a company that is trying to be the next Google."

" is a company that is trying to be the next Google."

" is a company that is trying to be the next ."

It is also possible to perform approximate matchings, but in cases like "Bug Apple", the solution would be ambiguous.

Improve this answer
$\endgroup$
0
$\begingroup$

One way to do so is as follows:

  1. Sort the company names from longest to shortest.

  2. For each company name $c$:

    a. Find all the substrings of the input string that equal $c$ and don't use any characters from a previous occurrence of a company name.

    b. If some substring exists, add $c$ to the solution.

This strategy works if you're trying to solve the problem you've stated. But if you want a more robust solution, you should look into using natural language processing tools like Python's NLTK. These tools allow you to take syntax and context into account, and might help you tell the difference between "I ate a big apple", and "I bought shares in Big Apple".

Improve this answer
$\endgroup$
2
  • $\begingroup$ This doesn't fully solve the problem, IMO. Suppose there are multiple occurrences of $c$, which one do you choose? Choosing all of them would lead to unnecessarily having to discard some other future company names. Choosing any one of those occurrences arbitrarily would also not work as one occurrence might block a more preferred company name in the future than another one, and so you'd want to avoid choosing that. But the obvious greedy solution that this leads to, "Pick the occurrence such that picking it blocks the smallest future company name", also doesn't work. $\endgroup$
    – CodeChef
    Commented Apr 12, 2020 at 1:58
  • $\begingroup$ That greedy doesn't work because there might have been another occurrence which blocks a more preferred company name in the future, but the blockage of that future company name might have been inevitable because of some other company name that you'd choose in between these two. And once you take this inevitability into consideration, the preference between the occurrences might change. And so on - you can take this down a deep rabbit hole. $\endgroup$
    – CodeChef
    Commented Apr 12, 2020 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.