Longest Common Subsequence using bit operations?

Revision en3, by ClosetNarcissist, 2024-03-24 17:40:03

Recently i did Leetcode Longest Common Subsequence problem. I used the basic dp approach and solved it in 18 ms using 12 mb space. After that i decided to check the fastest solutions for the problem and got this code

Fastest LCS code

I submitted it and it ran in 4 ms using 7.5 mb space. I tried to deconstruct the algorithm and understand how it was working. I cleaned the code a bit and got it to run in 3 ms, but I still could not understand it.

My optimized code

I could not find any relevant blogs explaining it. Can anyone help me understand how this works or link any blogs. Thanks.

Tags longest common substring, string, lcs, bit

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ClosetNarcissist 2024-03-24 17:40:03 13
en2 English ClosetNarcissist 2024-03-23 22:07:27 22 Tiny change: 'ommon Substring](https://' -> 'ommon Subsequence](https://'
en1 English ClosetNarcissist 2024-03-23 21:48:14 3190 Initial revision (published)