Skip to content

2060. Check if an Original String Exists Given Two Encoded Strings

  • Time: $O(|\texttt{s1}||\texttt{s1}| \cdot 2000)$
  • Space: $O(|\texttt{s1}||\texttt{s1}| \cdot 2000)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
 public:
  bool possiblyEquals(string s1, string s2) {
    dp.resize(s1.length() + 1,
              vector<unordered_map<int, bool>>(s2.length() + 1));
    return f(s1, s2, 0, 0, 0);
  }

 private:
  vector<vector<unordered_map<int, bool>>> dp;

  bool f(const string& s1, const string& s2, int i, int j, int paddingDiff) {
    // Return true if s1[i:] matches s2[j:] with given padding difference
    // I := s1's index
    // J := s2's index
    // PaddingDiff := signed padding, if positive, s1 has a positive number of
    //                offset bytes relative to s2
    if (dp[i][j].count(paddingDiff))
      return dp[i][j][paddingDiff];
    if (i == s1.length() && j == s2.length())
      return paddingDiff == 0;
    if (i < s1.length() && isdigit(s1[i])) {
      // Add padding on s1
      const int nextLetterIndex = getNextLetterIndex(s1, i);
      for (const int num : getNums(s1.substr(i, nextLetterIndex - i)))
        if (f(s1, s2, nextLetterIndex, j, paddingDiff + num))
          return true;
    } else if (j < s2.length() && isdigit(s2[j])) {
      // Add padding on s2
      const int nextLetterIndex = getNextLetterIndex(s2, j);
      for (const int num : getNums(s2.substr(j, nextLetterIndex - j)))
        if (f(s1, s2, i, nextLetterIndex, paddingDiff - num))
          return true;
    } else if (paddingDiff > 0) {
      // S1 has more padding, j needs to catch up
      if (j < s2.length())
        return f(s1, s2, i, j + 1, paddingDiff - 1);
    } else if (paddingDiff < 0) {
      // S2 has more padding, i needs to catch up
      if (i < s1.length())
        return f(s1, s2, i + 1, j, paddingDiff + 1);
    } else {  // PaddingDiff == 0
      // No padding difference, consue the next letter
      if (i < s1.length() && j < s2.length() && s1[i] == s2[j])
        return f(s1, s2, i + 1, j + 1, 0);
    }
    return dp[i][j][paddingDiff] = false;
  }

  int getNextLetterIndex(const string& s, int i) {
    int j = i;
    while (i < s.length() && isdigit(s[j]))
      ++j;
    return j;
  }

  vector<int> getNums(const string& s) {
    vector<int> nums{stoi(s)};
    if (s.length() == 2) {
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 1)));
    } else if (s.length() == 3) {
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 2)));
      nums.push_back(stoi(s.substr(0, 2)) + stoi(s.substr(2, 1)));
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 1)) +
                     stoi(s.substr(2, 1)));
    }
    return nums;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
  public boolean possiblyEquals(String s1, String s2) {
    dp = new Map[s1.length() + 1][s2.length() + 1];
    for (int i = 0; i <= s1.length(); ++i)
      for (int j = 0; j <= s2.length(); ++j)
        dp[i][j] = new HashMap<>();
    return f(s1, s2, 0, 0, 0);
  }

  private Map<Integer, Boolean>[][] dp;

  private boolean f(final String s1, final String s2, int i, int j, int paddingDiff) {
    // Return true if s1[i:] matches s2[j:] with given padding difference
    // I := s1's index
    // J := s2's index
    // PaddingDiff := signed padding, if positive, s1 has a positive number of
    //                offset bytes relative to s2
    if (dp[i][j].containsKey(paddingDiff))
      return dp[i][j].get(paddingDiff);
    if (i == s1.length() && j == s2.length())
      return paddingDiff == 0;
    if (i < s1.length() && Character.isDigit(s1.charAt(i))) {
      // Add padding on s1
      final int nextLetterIndex = getNextLetterIndex(s1, i);
      for (final int num : getNums(s1.substring(i, nextLetterIndex)))
        if (f(s1, s2, nextLetterIndex, j, paddingDiff + num))
          return true;
    } else if (j < s2.length() && Character.isDigit(s2.charAt(j))) {
      // Add padding on s2
      final int nextLetterIndex = getNextLetterIndex(s2, j);
      for (final int num : getNums(s2.substring(j, nextLetterIndex)))
        if (f(s1, s2, i, nextLetterIndex, paddingDiff - num))
          return true;
    } else if (paddingDiff > 0) {
      // S1 has more padding, j needs to catch up
      if (j < s2.length())
        return f(s1, s2, i, j + 1, paddingDiff - 1);
    } else if (paddingDiff < 0) {
      // S2 has more padding, i needs to catch up
      if (i < s1.length())
        return f(s1, s2, i + 1, j, paddingDiff + 1);
    } else { // PaddingDiff == 0
      // No padding difference, consue the next letter
      if (i < s1.length() && j < s2.length() && s1.charAt(i) == s2.charAt(j))
        return f(s1, s2, i + 1, j + 1, 0);
    }
    dp[i][j].put(paddingDiff, false);
    return false;
  }

  private int getNextLetterIndex(final String s, int i) {
    int j = i;
    while (j < s.length() && Character.isDigit(s.charAt(j)))
      ++j;
    return j;
  }

  private List<Integer> getNums(final String s) {
    List<Integer> nums = new ArrayList<>(Arrays.asList(Integer.parseInt(s)));
    if (s.length() == 2) {
      nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 2)));
    } else if (s.length() == 3) {
      nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 3)));
      nums.add(Integer.parseInt(s.substring(0, 2)) + Integer.parseInt(s.substring(2, 3)));
      nums.add(Integer.parseInt(s.substring(0, 1)) + Integer.parseInt(s.substring(1, 2)) +
               Integer.parseInt(s.substring(2, 3)));
    }
    return nums;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
  def possiblyEquals(self, s1: str, s2: str) -> bool:
    def getNums(s: str) -> Set[int]:
      nums = {int(s)}
      for i in range(1, len(s)):
        nums |= {x + y for x in getNums(s[:i]) for y in getNums(s[i:])}
      return nums

    def getNextLetterIndex(s: str, i: int) -> int:
      j = i
      while j < len(s) and s[j].isdigit():
        j += 1
      return j

    @functools.lru_cache(None)
    def dp(i: int, j: int, paddingDiff: int) -> bool:
      """
      Return True if s1[i:] matches s2[j:] with given padding difference
      i := s1's index
      j := s2's index
      paddingDiff := signed padding, if positive, s1 has a positive number of
                     offset bytes relative to s2
      """
      if i == len(s1) and j == len(s2):
        return paddingDiff == 0
      # Add padding on s1
      if i < len(s1) and s1[i].isdigit():
        nextLetterIndex = getNextLetterIndex(s1, i)
        for num in getNums(s1[i:nextLetterIndex]):
          if dp(nextLetterIndex, j, paddingDiff + num):
            return True
      # Add padding on s2
      elif j < len(s2) and s2[j].isdigit():
        nextLetterIndex = getNextLetterIndex(s2, j)
        for num in getNums(s2[j:nextLetterIndex]):
          if dp(i, nextLetterIndex, paddingDiff - num):
            return True
      # S1 has more padding, j needs to catch up
      elif paddingDiff > 0:
        if j < len(s2):
          return dp(i, j + 1, paddingDiff - 1)
      # S2 has more padding, i needs to catch up
      elif paddingDiff < 0:
        if i < len(s1):
          return dp(i + 1, j, paddingDiff + 1)
      # No padding difference, consume the next letter
      else:  # PaddingDiff == 0
        if i < len(s1) and j < len(s2) and s1[i] == s2[j]:
          return dp(i + 1, j + 1, 0)
      return False

    return dp(0, 0, 0)