3
\$\begingroup\$

There is an source and target.

example:

source:[a,b,e,d,s,t,c,v,t]

target:[a,e,v,g,r,b,c,v,t]

target and source have same number of elements.

how can I count elements in source ordered correctly according to target?

so, target means that elements in source should be ordered in target's order.

and count maximum number of properly ordered elements in source.

so the answer for example is 5 (a,b,c,v,t).

of course there are two elements in order like (a,e),(a,b) but out put should be maximum elements.

how can I do it neat and compactly?

My code

I used combinations, counting from max element number to 0.

n=len(target)
k=1
for check in range(n,-1,-1):
            while k!=0:
                for j in combinations(souce,check):
                    if j in combinations(target,check):
                        answer_co.append(check)
                        k=0
                        break
\$\endgroup\$
8
  • 1
    \$\begingroup\$ This problem can be solved more efficiently using dynamic programming. \$\endgroup\$
    – GZ0
    Nov 15, 2020 at 9:57
  • \$\begingroup\$ @GZ0 how can i do that?? \$\endgroup\$
    – sherloock
    Nov 15, 2020 at 16:10
  • \$\begingroup\$ Have you learned DP before? If so, are you able to identify the overlapping subproblem and come up with a recurrence? \$\endgroup\$
    – GZ0
    Nov 15, 2020 at 17:22
  • \$\begingroup\$ @GZ0 I searched for it and i understood what it is. Is this same with recursive programming? \$\endgroup\$
    – sherloock
    Nov 16, 2020 at 6:32
  • 1
    \$\begingroup\$ This is a classical problem. You can search for "longest common subsequence". \$\endgroup\$
    – GZ0
    Nov 16, 2020 at 21:54

1 Answer 1

2
\$\begingroup\$

This is a classical LCS problem, which can be solved in DP as suggested by earlier post. Time Complexity of the implementation is O(mn) which is much better than the original code implementation. (An exercise for the reader to study. ;-)

The next code fragment assumes that the source/target are both strings.

Here is the DP approach:

class Solution:

def lcs(self, source: str, target: str) -> int:
    n,  m = len(source), len(target)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n):
        for j in range(m):
            if source[i] == target[j]:
                dp[i + 1][j + 1]= dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    return dp[-1][-1]
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Formatted your answer, but I don't know what to do with "(recursion way)". Please try and think of a better sentence for that and remove the parentheses. \$\endgroup\$ Dec 7, 2020 at 2:40
  • \$\begingroup\$ Welcome to the Code Review Community. This community is primarily about improving the original posters ability to code, as such meaningful observations about the code posted in the question are more important than providing alternate code only solutions. Code only alternate solutions are quite often down voted and deleted by the community. The only meaningful observation in your post is This is a classical LCS problem, which can be solved in DP as suggested by earlier post. Why is the code you have posted any better than the code in the original post (update your answer with the reason). \$\endgroup\$
    – pacmaninbw
    Dec 7, 2020 at 17:10
  • \$\begingroup\$ Agreed. Add the Run Time info. (still learning how to put info. together...) Thx \$\endgroup\$
    – Daniel Hao
    Dec 7, 2020 at 19:25
  • \$\begingroup\$ @DanielHao what does dp[i][j] stand for? Explain that in your answer. \$\endgroup\$ Dec 8, 2020 at 2:53
  • \$\begingroup\$ DP == Dynamic Programming . See this reference - en.wikipedia.org/wiki/Dynamic_programming \$\endgroup\$
    – Daniel Hao
    Dec 8, 2020 at 3:04

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.