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
|
use std::collections::HashMap;
impl Solution {
pub fn possibly_equals(s1: String, s2: String) -> bool {
fn dfs(i: usize, j: usize, diff: i32, s1: &Vec<u8>, s2: &Vec<u8>, memo: &mut HashMap<(usize, usize, i32), bool>) -> bool {
if let Some(&v) = memo.get(&(i, j, diff)) { return v; }
let n = s1.len();
let m = s2.len();
if i == n && j == m { return diff == 0; }
if i < n && s1[i].is_ascii_digit() {
let mut v = 0;
for k in i..(i+3).min(n) {
if !s1[k].is_ascii_digit() { break; }
v = v * 10 + (s1[k] - b'0') as i32;
if dfs(k+1, j, diff+v, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
}
}
if j < m && s2[j].is_ascii_digit() {
let mut v = 0;
for k in j..(j+3).min(m) {
if !s2[k].is_ascii_digit() { break; }
v = v * 10 + (s2[k] - b'0') as i32;
if dfs(i, k+1, diff-v, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
}
}
if diff > 0 && i < n && !s1[i].is_ascii_digit() {
if dfs(i+1, j, diff-1, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
}
if diff < 0 && j < m && !s2[j].is_ascii_digit() {
if dfs(i, j+1, diff+1, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
}
if diff == 0 && i < n && j < m && !s1[i].is_ascii_digit() && !s2[j].is_ascii_digit() && s1[i] == s2[j] {
if dfs(i+1, j+1, 0, s1, s2, memo) { memo.insert((i, j, diff), true); return true; }
}
memo.insert((i, j, diff), false);
false
}
let s1b = s1.as_bytes().to_vec();
let s2b = s2.as_bytes().to_vec();
let mut memo = HashMap::new();
dfs(0, 0, 0, &s1b, &s2b, &mut memo)
}
}
|