Grokking Oracle Coding Interview
Vote

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLCSLength(self, s1, s2):
    m = len(s1) + 1
    n = len(s2) + 1
    table = [[0] * n for _ in range(m)]
    
    for i in range(1, m):
      for j in range(1, n):
        if s1[i - 1] == s2[j - 1]:
          table[i][j] = table[i - 1][j - 1] + 1
        else:
          table[i][j] = max(table[i][j - 1],  table[i - 1][j])
        
    return table[-1][-1]
S

Shan

· 4 years ago

What is time and space complexity of top down with memo?

G

Gary

· 4 years ago

In bottom-up solution,

"If the character s1[i] matches s2[j], the length of the common subsequence would be one plus the length of the common subsequence till the i-1 and j-1 indexes in the two respective strings," which is intuitive.

But the actual code checks for s1[i-1] ==s2[i-2]:

for i in range(1, n1+1): for j in range(1, n2+1): if s1[i - 1] == s2[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1]

When i try to write it as follows, I get 4 instead of 5 for "passport"/"ppsspt"

max_length = 0 for s1_idx in range (1, len(s1)): for s2_idx in range(1, len(s2)): if s1[s1_idx] == s2[s2_idx]: dp[s1_idx][s2_idx] = 1 + dp[s1_idx-1][s2_idx-1] else: dp[s1_idx][s2_idx] = max(dp[s1_idx-1][s2_idx], dp[s1_idx][s2_idx-1])

max_length = max(max_length, dp[s1_idx][s2_idx])

return max_length

Is there a way to

Reading Progress

0%