Verbal arithmetic puzzle

Array Math String Backtracking

34.9% acceptance

Feb 25, 2026

528

138

Given an equation, represented by words on the left side and the result on the right side. You need to check if the equation is solvable under the following rules: Each character is decoded as one digit (0 - 9). No two characters can map to the same digit. Each words[i] and result are decoded as one number without leading zeros. Sum of numbers on the left side (words) will equal to the number on the right side (result). Return true if the equation is solvable, otherwise return false.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_solvable(words: Vec<String>, result: String) -> bool {
    let mut char_set = std::collections::HashSet::new();
    let mut no_zero = std::collections::HashSet::new();
    let mut coeff: std::collections::HashMap<u8, i64> = std::collections::HashMap::new();

    for w in &words {
      let bytes = w.as_bytes();
      if bytes.len() > 1 { no_zero.insert(bytes[0]); }
      let mut mul = 1i64;
      for &b in bytes.iter().rev() {
        *coeff.entry(b).or_insert(0) += mul;
        char_set.insert(b);
        mul *= 10;
      }
    }
    let rbytes = result.as_bytes();
    if rbytes.len() > 1 { no_zero.insert(rbytes[0]); }
    let mut mul = 1i64;
    for &b in rbytes.iter().rev() {
      *coeff.entry(b).or_insert(0) -= mul;
      char_set.insert(b);
      mul *= 10;
    }

    // Sort by absolute coefficient descending for pruning
    let mut chars: Vec<u8> = char_set.into_iter().collect();
    chars.sort_by(|a, b| coeff[b].abs().cmp(&coeff[a].abs()));

    let coeff_list: Vec<i64> = chars.iter().map(|c| coeff[c]).collect();
    let no_zero_list: Vec<bool> = chars.iter().map(|c| no_zero.contains(c)).collect();

    fn bt(idx: usize, sum: i64, coeff_list: &[i64], no_zero_list: &[bool], used: &mut [bool; 10]) -> bool {
      if idx == coeff_list.len() { return sum == 0; }
      // Pruning: compute min/max reachable sum from remaining
      let mut min_rem = 0i64;
      let mut max_rem = 0i64;
      let mut avail: Vec<i64> = (0..10).filter(|&d| !used[d as usize]).collect();
      avail.sort();
      for k in idx..coeff_list.len() {
        let c = coeff_list[k];
        if c > 0 { max_rem += c * avail[avail.len() - 1]; min_rem += c * avail[0]; }
        else { max_rem += c * avail[0]; min_rem += c * avail[avail.len() - 1]; }
      }
      if sum + min_rem > 0 || sum + max_rem < 0 { return false; }

      for d in 0..10usize {
        if used[d] { continue; }
        if d == 0 && no_zero_list[idx] { continue; }
        used[d] = true;
        if bt(idx + 1, sum + coeff_list[idx] * d as i64, coeff_list, no_zero_list, used) {
          used[d] = false;
          return true;
        }
        used[d] = false;
      }
      false
    }

    let mut used = [false; 10];
    bt(0, 0, &coeff_list, &no_zero_list, &mut used)
  }
}