Question

2451. Odd String Difference

中文文档

Description

You are given an array of equal-length strings words. Assume that the length of each string is n.

Each string words[i] can be converted into a difference integer array difference[i] of length n - 1 where difference[i][j] = words[i][j+1] - words[i][j] where 0 <= j <= n - 2. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a' is 0, 'b' is 1, and 'z' is 25.

• For example, for the string "acb", the difference integer array is [2 - 0, 1 - 2] = [2, -1].

All the strings in words have the same difference integer array, except one. You should find that string.

Return_ the string in _words_ that has different difference integer array._

 

Example 1:

Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation: 
- The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].
- The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1].
- The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1]. 
The odd array out is [1, 1], so we return the corresponding string, "abc".

Example 2:

Input: words = ["aaa","bob","ccc","ddd"]
Output: "bob"
Explanation: All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].

 

Constraints:

• 3 <= words.length <= 100
• n == words[i].length
• 2 <= n <= 20
• words[i] consists of lowercase English letters.

Solutions

Solution 1: Hash Table Simulation

We use a hash table $d$ to maintain the mapping relationship between the difference array of the string and the string itself, where the difference array is an array composed of the differences of adjacent characters in the string. Since the problem guarantees that except for one string, the difference arrays of other strings are the same, we only need to find the string with a different difference array.

The time complexity is $O(m \times n)$, and the space complexity is $O(m + n)$. Here, $m$ and $n$ are the length of the string and the number of strings, respectively.

class Solution:
  def oddString(self, words: List[str]) -> str:
    d = defaultdict(list)
    for s in words:
      t = tuple(ord(b) - ord(a) for a, b in pairwise(s))
      d[t].append(s)
    return next(ss[0] for ss in d.values() if len(ss) == 1)

class Solution {
  public String oddString(String[] words) {
    var d = new HashMap<String, List<String>>();
    for (var s : words) {
      int m = s.length();
      var cs = new char[m - 1];
      for (int i = 0; i < m - 1; ++i) {
        cs[i] = (char) (s.charAt(i + 1) - s.charAt(i));
      }
      var t = String.valueOf(cs);
      d.putIfAbsent(t, new ArrayList<>());
      d.get(t).add(s);
    }
    for (var ss : d.values()) {
      if (ss.size() == 1) {
        return ss.get(0);
      }
    }
    return "";
  }
}

class Solution {
public:
  string oddString(vector<string>& words) {
    unordered_map<string, vector<string>> cnt;
    for (auto& w : words) {
      string d;
      for (int i = 0; i < w.size() - 1; ++i) {
        d += (char) (w[i + 1] - w[i]);
        d += ',';
      }
      cnt[d].emplace_back(w);
    }
    for (auto& [_, v] : cnt) {
      if (v.size() == 1) {
        return v[0];
      }
    }
    return "";
  }
};

func oddString(words []string) string {
  d := map[string][]string{}
  for _, s := range words {
    m := len(s)
    cs := make([]byte, m-1)
    for i := 0; i < m-1; i++ {
      cs[i] = s[i+1] - s[i]
    }
    t := string(cs)
    d[t] = append(d[t], s)
  }
  for _, ss := range d {
    if len(ss) == 1 {
      return ss[0]
    }
  }
  return ""
}

function oddString(words: string[]): string {
  const d: Map<string, string[]> = new Map();
  for (const s of words) {
    const cs: number[] = [];
    for (let i = 0; i < s.length - 1; ++i) {
      cs.push(s[i + 1].charCodeAt(0) - s[i].charCodeAt(0));
    }
    const t = cs.join(',');
    if (!d.has(t)) {
      d.set(t, []);
    }
    d.get(t)!.push(s);
  }
  for (const [_, ss] of d) {
    if (ss.length === 1) {
      return ss[0];
    }
  }
  return '';
}

use std::collections::HashMap;
impl Solution {
  pub fn odd_string(words: Vec<String>) -> String {
    let n = words[0].len();
    let mut map: HashMap<String, (bool, usize)> = HashMap::new();
    for (i, word) in words.iter().enumerate() {
      let mut k = String::new();
      for j in 1..n {
        k.push_str(&(word.as_bytes()[j] - word.as_bytes()[j - 1]).to_string());
        k.push(',');
      }
      let new_is_only = !map.contains_key(&k);
      map.insert(k, (new_is_only, i));
    }
    for (is_only, i) in map.values() {
      if *is_only {
        return words[*i].clone();
      }
    }
    String::new()
  }
}

Solution 2

use std::collections::HashMap;

impl Solution {
  pub fn odd_string(words: Vec<String>) -> String {
    let mut h = HashMap::new();

    for w in words {
      let bytes: Vec<i32> = w
        .bytes()
        .zip(w.bytes().skip(1))
        .map(|(current, next)| (next - current) as i32)
        .collect();

      let s: String = bytes
        .iter()
        .map(|&b| char::from(b as u8))
        .collect();

      h.entry(s)
        .or_insert(vec![])
        .push(w);
    }

    for strs in h.values() {
      if strs.len() == 1 {
        return strs[0].clone();
      }
    }

    String::from("")
  }
}