# Checking whether a word is Hamming-isometric in linear time

arXiv: https://arxiv.org/abs/2106.10541 · HTML: https://mlsanity.com/paper/2106.10541/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2021.

## Built on by (most cited first, 1 of 1)

- [On the k-Hamming and k-Edit Distances](https://mlsanity.com/paper/2306.09144/) (2023)

## Abstract (arXiv)

A finite word f is Hamming-isometric if for any two word u and v of same length avoiding f, u can be transformed into v by changing one by one all the letters on which u differs from v, in such a way that all of the new words obtained in this process also avoid~f. Words which are not Hamming-isometric have been characterized as words having a border with two mismatches. We derive from this characterization a linear-time algorithm to check whether a word is Hamming-isometric. It is based on pattern matching algorithms with k mismatches. Lee-isometric words over a four-letter alphabet have been characterized as words having a border with two Lee-errors. We derive from this characterization a linear-time algorithm to check whether a word over an alphabet of size four is Lee-isometric.