Back to Repositories

Testing Shortest Common Supersequence Algorithm in javascript-algorithms

This test suite validates the shortest common supersequence algorithm implementation, focusing on finding the shortest sequence that contains both input sequences as subsequences. The tests cover various scenarios including empty longest common subsequences and complex string patterns.

Test Coverage Overview

The test suite provides comprehensive coverage of the shortestCommonSupersequence function with multiple test cases.

Key test scenarios include:

Empty LCS between sequences
Simple sequences with common elements
Complex sequences with multiple common subsequences
Edge cases with repeated characters

Implementation Analysis

The testing approach utilizes Jest’s expect assertions to verify algorithm outputs against known solutions. Each test case clearly documents the expected Longest Common Subsequence (LCS) in comments, making the test intentions transparent.

The implementation uses array-based sequence comparisons with Jest’s toEqual matcher for precise array equality verification.

Technical Details

Testing Framework: Jest
Test Structure: Describe/It blocks
Assertion Style: Expect statements
Data Types: Arrays of characters
Comparison Method: Deep equality checking

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Clear test case documentation
Comprehensive edge case coverage
Consistent test structure
Well-documented expected outputs
Focused test scenarios with specific assertions

trekhleb/javascript-algorithms

src/algorithms/sets/shortest-common-supersequence/__test__/shortestCommonSupersequence.test.js

            
import shortestCommonSupersequence from '../shortestCommonSupersequence';

describe('shortestCommonSupersequence', () => {
  it('should find shortest common supersequence of two sequences', () => {
    // LCS (longest common subsequence) is empty
    expect(shortestCommonSupersequence(
      ['A', 'B', 'C'],
      ['D', 'E', 'F'],
    )).toEqual(['A', 'B', 'C', 'D', 'E', 'F']);

    // LCS (longest common subsequence) is "EE"
    expect(shortestCommonSupersequence(
      ['G', 'E', 'E', 'K'],
      ['E', 'K', 'E'],
    )).toEqual(['G', 'E', 'K', 'E', 'K']);

    // LCS (longest common subsequence) is "GTAB"
    expect(shortestCommonSupersequence(
      ['A', 'G', 'G', 'T', 'A', 'B'],
      ['G', 'X', 'T', 'X', 'A', 'Y', 'B'],
    )).toEqual(['A', 'G', 'G', 'X', 'T', 'X', 'A', 'Y', 'B']);

    // LCS (longest common subsequence) is "BCBA".
    expect(shortestCommonSupersequence(
      ['A', 'B', 'C', 'B', 'D', 'A', 'B'],
      ['B', 'D', 'C', 'A', 'B', 'A'],
    )).toEqual(['A', 'B', 'D', 'C', 'A', 'B', 'D', 'A', 'B']);

    // LCS (longest common subsequence) is "BDABA".
    expect(shortestCommonSupersequence(
      ['B', 'D', 'C', 'A', 'B', 'A'],
      ['A', 'B', 'C', 'B', 'D', 'A', 'B', 'A', 'C'],
    )).toEqual(['A', 'B', 'C', 'B', 'D', 'C', 'A', 'B', 'A', 'C']);
  });
});