392. Is Subsequence

public class Solution {
    public bool IsSubsequence(string s, string t) {
        int leftBound = s.Length, rightBound = t.Length;
        int pLeft = 0, pRight = 0;
        while (pLeft < leftBound && pRight < rightBound) {
            if (s[pLeft] == t[pRight]) {
                pLeft += 1;
            }
            pRight += 1;
        }
        return pLeft == leftBound;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsSubsequence(string s, string t) {
        int leftBound = s.size(), rightBound = t.size();
        int pLeft = 0, pRight = 0;
        while (pLeft < leftBound && pRight < rightBound) {
            if (s[pLeft] == t[pRight]) {
                pLeft += 1;
            }
            pRight += 1;
        }
        return pLeft == leftBound;
    }
}

class Solution {
    public boolean isSubsequence(String s, String t) {
        int leftBound = s.length(), rightBound = t.length();
        int pLeft = 0, pRight = 0;

        while (pLeft < leftBound && pRight < rightBound) {
            if (s.charAt(pLeft) == t.charAt(pRight)) {
                pLeft += 1;
            }
            pRight += 1;
        }
        return pLeft == leftBound;
    }
}

function isSubsequence(s, t) {
    let leftBound = s.length, rightBound = t.length;
    let pLeft = 0, pRight = 0;

    while (pLeft < leftBound && pRight < rightBound) {
        if (s[pLeft] === t[pRight]) {
            pLeft += 1;
        }
        pRight += 1;
    }
    return pLeft === leftBound;
}

// Example usage
console.log(isSubsequence("abc", "ahbgdc")); // Output: true
console.log(isSubsequence("axc", "ahbgdc")); // Output: false

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        left_bound, right_bound = len(s), len(t)
        p_left, p_right = 0, 0

        while p_left < left_bound and p_right < right_bound:
            if s[p_left] == t[p_right]:
                p_left += 1
            p_right += 1
        
        return p_left == left_bound

package main

import "fmt"

func isSubsequence(s string, t string) bool {
    leftBound, rightBound := len(s), len(t)
    pLeft, pRight := 0, 0

    for pLeft < leftBound && pRight < rightBound {
        if s[pLeft] == t[pRight] {
            pLeft++
        }
        pRight++
    }
    return pLeft == leftBound
}

func main() {
    s := "abc"
    t := "ahbgdc"
    fmt.Println(isSubsequence(s, t)) // Output: true

    s = "axc"
    t = "ahbgdc"
    fmt.Println(isSubsequence(s, t)) // Output: false
}

Algorithm

Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов.

Перемещайте указатели в зависимости от совпадения символов. Если символы на текущих позициях указателей совпадают, переместите оба указателя на один шаг вперед. Если символы не совпадают, переместите только правый указатель целевой строки.

Итерация завершается, когда один из указателей выходит за пределы своей строки. Если в конце итерации все символы исходной строки были найдены в целевой строке, исходная строка является подпоследовательностью целевой строки.

😎