CODEWITHSUNDEEP
javacollections
membersound
membersound

Reputation: 86727

How to extract non-intersection part of two ordered lists?

I want to join two string lists. Both lists have a fixed order.

Problem: the 2nd list contains partially the "end" of the 1st list. I never know how many items of the end of the first list are on top of the 2nd list.

Example:

1st list:

testa
testb
testc
testa
testd
testg

2nd list:

testa //from 1st
testd //from 1st
testg //from 1st
textf
testc
testb
testa

Here you see the first elements in the 2nd list are "continued" from the 1st list. I thus want to remove these 3 items from the 2nd list and then join both lists.

Question: how is such an operation called? Probably there are already frameworks like apache-commons CollectionUtils that might perform those operations?

Upvotes: 0

Views: 45

Answers (1)

assylias
assylias

Reputation: 328598

I don't know how it's called (although it looks a little bit like the Longest common subsequence problem, but with additional constraints) and I don't think you'll find a built-in method. But you could write it:

  1. list1 of length n1 and list2 of length n2
  2. start from item i=max(0, n1-n2) and check if list1(i) == list2(n1-i-1)
  3. keep incrementing i until you find a match
  4. compare the sublists list1(i:n1) and list2(0:n1-i-1) - if they match you have found what you wanted, otherwise go back to 3

That can probably be made more efficient.

Upvotes: 2

Related Questions