Is Subsequence - C Solution

1. Introduction

This post tackles a classic problem in string processing - determining if one string is a subsequence of another. The challenge lies in verifying whether all the characters of the first string appear in the second string while maintaining their relative order. This problem is fundamental in understanding string manipulation and pattern matching algorithms.

Problem

Given two strings s and t, the task is to return true if s is a subsequence of t, or false otherwise. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

2. Solution Steps

1. Initialize two pointers, one for each string.

2. Iterate through the characters of string t.

3. When a character in t matches the current character in s, move the pointer in s forward.

4. If the pointer in s reaches the end of the string, it means all characters of s were found in t in order.

5. Return true if all characters of s are found in t, otherwise return false.

3. Code Program

#include <stdio.h>
#include <string.h>

// Function to check if s is a subsequence of t
int isSubsequence(char* s, char* t) {
    int sIndex = 0, tIndex = 0;

    while (s[sIndex] != '\0' && t[tIndex] != '\0') {
        if (s[sIndex] == t[tIndex]) {
            sIndex++; // Move forward in s
        }
        tIndex++; // Always move forward in t
    }
    return s[sIndex] == '\0'; // Check if all characters in s were found
}

// Main function to test the isSubsequence function
int main() {
    char s1[] = "abc";
    char t1[] = "ahbgdc";
    printf("Is Subsequence (Example 1): %s\n", isSubsequence(s1, t1) ? "true" : "false");

    char s2[] = "axc";
    char t2[] = "ahbgdc";
    printf("Is Subsequence (Example 2): %s\n", isSubsequence(s2, t2) ? "true" : "false");

    return 0;
}

Output:

Is Subsequence (Example 1): true
Is Subsequence (Example 2): false

Explanation:

1. Initialize pointers for both s and t.

2. Iterate through t and compare with the current character of s.

3. Move the pointer in s forward only if a matching character is found in t.

4. Continue until all characters in s are checked or t is fully traversed.

5. Return true if end of s is reached, indicating all its characters were found in sequence in t.

6. The main function tests the isSubsequence function with two examples and prints the results.