Longest common subsequence program in swift

In Sets 1 and 2, we addressed Overlapping Subproblems and Optimal Substructure Properties, respectively. In Set 3, we also talked about an example problem. Let’s have a look at another problem that can be solved using Dynamic Programming: the Longest Common Subsequence (LCS) problem.

Finding the length of the longest subsequence present in both sequences is the LCS problem statement. A subsequence is a series of events that occur in the same order but are not necessarily contiguous. Subsequences of “abcdefg” include “abc”, “abg”, “bdf”, “aeg”, “acefg”, and so on.

The longest here indicates that the subsequence should be the most significant. The term “common” refers to the fact that some of the character

> aabbccdd abbcd
    In above example "abbcd" is the Longest common subsequence.
>route  out
    "out" will be the Longest common subsequence here.

s in the two strings are the same. The term “subsequence” refers to the extraction of some characters from a string that is written in ascending order to generate a subsequence.

The longest common subsequence for strings ACFGHD and ABFHD is AFHD. The following function is used to discover the longest common subsequence of two strings.

Given above strings "ABCB" and "ABDCAB", the output matrix of lcs Length in the following:

|   | Ø | A | B | D | C | A | B |
| Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 | 1 | 1 |  
| B | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| C | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| B | 0 | 1 | 2 | 2 | 3 | 3 | 4 |

I’ve included a Program code for the longest common subsequence problem as well as a video tutorial to assist you understand the LCS method.

The pseudo code for the Longest common subsequence method is

function func(j, k):
    if j == 0 or k == 0:
        return 0
    else if A[j] == B[k]:
        return 1 + func(j-1, k-1)
    else:
        return maximum(func(j-1, k), func(j, k-1))

// the answer is now func(n, m)

Swift code for the LCS

func lengthLCS(_ lcs: String) -> [[Int]] {

  var arr = [[Int]](repeating: [Int](repeating: 0, count: other.characters.count+1), count: self.characters.count+1)

  for (j, selfChar) in self.characters.enumerated() {
	for (k, otherChar) in other.characters.enumerated() {
	  if otherChar == selfChar {
		// Common char found, add 1 to highest lcs found so far.
		arr[j+1][k+1] = arr[j][k] + 1
	  } else {
		// Not a match, propagates highest lcs length found so far.
		arr[i+1][j+1] = maximum(arr[j][k+1], arr[j+1][k])
	  }
	}
  }

  return arr
}

Backtracking code for LCS

func backtracklcs(_ arr: [[Int]]) -> String {
  var j = self.characters.count
  var k = other.characters.count
  
  var charSequence = self.endIndex
  
  var lcs = String()
  
  while j >= 1 && k >= 1 {
          // Indicates no change in propagation: no new char was added to lcs.
	if arr[j][k] == arr[j][k - 1] {
	  j -= 1
	}
          // Indicates no change in propagation: no new char was added to lcs.
	else if arr[j][k] == arr[j - 1][k] {
	  j -= 1
	  charSequence = self.index(before: charSequence)
	}
              // The values on the left and above differ from the value in the current cell. 
              // The length of the lcs has been increased by one.
	else {
	  j -= 1
	  k -= 1
	  charSequence = self.index(before: charSequence)
	  lcs.append(self[charSequence])
	}
  }
  
  return String(lcs.characters.reversed())
}

Putting it together lenghtLCS() and backtrackLCS() to find the LCS of the 2 string

extension String {
  public func longestCommonSubsequenceinswift(_ lcs: String) -> String {

    func Lengthlcs(_ lcs: String) -> [[Int]] {
      ...
    }
    
    func backtracklcs(_ arr: [[Int]]) -> String {
      ...
    }

    return backtracklcs(Lengthlcs(lcs))
  }
}

The two auxiliary functions are contained inside the main longestCommonSubsequence() function to keep things neat.

let x = "ABBDC"
let y = "ABDDCAB"
x.longestCommonSubsequence(y)   // "ABDCB"

let z = "JKLM"
x.longestCommonSubsequence(c)   // "" (no common  subsequence found)

"Hello World".longestCommonSubsequence("Hey buddy")   // "He d"

SwitLCS extends Collection by locating the indices of the longest common subsequence with another collection.

The longest common subsequence (LCS) issue is the task of determining the longest subsequence that is shared by all sequences in a set of sequences (often just two sequences). It varies from issues involving the search for common substrings in that, unlike substrings, subsequences are not necessary to occupy consecutive locations inside the parent sequences.

We can install the Cocoa Pods in swift

CocoaPods

CocoaPods is the dependency management for Cocoa projects written in Swift and Objective-C. It includes over ten thousand libraries and may assist you in scaling your projects gracefully.

use_frameworks!

pod 'SwiftLCS'

Carthage creates your dependencies and offers binary frameworks, but you retain complete control over the structure and configuration of your project.

Add the following to your Cartfile:

github "Frugghi/SwiftLCS"

The Swift Package Manager is a tool for managing Swift code distribution. It integrates with the Swift build system to automate the download, compilation, and linking of dependencies.

Include SwiftLCS in your Package.

Dependencies that are urgent:

import PackageDescription

let package = Package(
    dependencies: [
        .Package(url: "https://github.com/Frugghi/SwiftLCS.git", majorVersion: 1, minor: 3)
    ]
)

We can import swiftlcs framework in the required file and also use it

import SwiftLCS

For string

let x = "aabbcdd"
let y = "abbc"

let z = x.longestCommonSubsequence(y) // abbc