Check if an original string exists given two encoded strings

String Dynamic Programming

43.5% acceptance

Feb 25, 2026

327

163

An original string, consisting of lowercase English letters, can be encoded by the following steps: Arbitrarily split it into a sequence of some number of non-empty substrings. Arbitrarily choose some elements (possibly none) of the sequence, and replace each with its length (as a numeric string). Concatenate the sequence as the encoded string. For example, one way to encode an original string "abcdefghijklmnop" might be: Split it as a sequence: ["ab", "cdefghijklmn", "o", "p"]. Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes ["ab", "12", "1", "p"]. Concatenate the elements of the sequence to get the encoded string: "ab121p". Given two encoded strings s1 and s2, consisting of lowercase English letters and digits 1-9 (inclusive), return true if there exists an original string that could be encoded as both s1 and s2. Otherwise, return false. Note: The test cases are generated such that the number of consecutive digits in s1 and s2 does not exceed 3.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn possibly_equals(s1: String, s2: String) -> bool {
    use std::collections::HashSet;
    let s1: Vec<u8> = s1.bytes().collect();
    let s2: Vec<u8> = s2.bytes().collect();
    let n1 = s1.len();
    let n2 = s2.len();

    // diff = virtual_pos_s1 - virtual_pos_s2
    // diff > 0: s1 has more chars to account for; s2 must consume from its side
    // diff < 0: s2 has more chars; s1 must consume
    let mut visited: HashSet<(usize, usize, i32)> = HashSet::new();
    let mut stack: Vec<(usize, usize, i32)> = vec![(0, 0, 0)];

    while let Some((i, j, diff)) = stack.pop() {
      if i == n1 && j == n2 {
        if diff == 0 {
          return true;
        }
        continue;
      }
      if !visited.insert((i, j, diff)) {
        continue;
      }

      if diff > 0 {
        // s1 has diff more chars. s2 must catch up.
        if j < n2 {
          if s2[j].is_ascii_lowercase() {
            stack.push((i, j + 1, diff - 1));
          } else {
            let mut num = 0i32;
            let mut jj = j;
            while jj < n2 && s2[jj].is_ascii_digit() {
              num = num * 10 + (s2[jj] - b'0') as i32;
              jj += 1;
              stack.push((i, jj, diff - num));
            }
          }
        }
      } else if diff < 0 {
        // s2 has -diff more chars. s1 must catch up.
        if i < n1 {
          if s1[i].is_ascii_lowercase() {
            stack.push((i + 1, j, diff + 1));
          } else {
            let mut num = 0i32;
            let mut ii = i;
            while ii < n1 && s1[ii].is_ascii_digit() {
              num = num * 10 + (s1[ii] - b'0') as i32;
              ii += 1;
              stack.push((ii, j, diff + num));
            }
          }
        }
      } else {
        // diff == 0: in sync
        if i < n1 && j < n2 {
          if s1[i].is_ascii_lowercase() && s2[j].is_ascii_lowercase() {
            if s1[i] == s2[j] {
              stack.push((i + 1, j + 1, 0));
            }
          }
        }
        if i < n1 && s1[i].is_ascii_digit() {
          let mut num = 0i32;
          let mut ii = i;
          while ii < n1 && s1[ii].is_ascii_digit() {
            num = num * 10 + (s1[ii] - b'0') as i32;
            ii += 1;
            stack.push((ii, j, num));
          }
        }
        if j < n2 && s2[j].is_ascii_digit() {
          let mut num = 0i32;
          let mut jj = j;
          while jj < n2 && s2[jj].is_ascii_digit() {
            num = num * 10 + (s2[jj] - b'0') as i32;
            jj += 1;
            stack.push((i, jj, -num));
          }
        }
      }
    }

    false
  }
}