# 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>(s2.length() + 1)); return f(s1, s2, 0, 0, 0); } private: vector>> 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 getNums(const string& s) { vector 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[][] 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 getNums(final String s) { List 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)