Practice Now
string comparison
similar string search
string matching
text similarity
algorithm

string comparison with the most similar string

Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms
Algorithms

Introduction

Finding the most similar string from a set of candidates is a common task in spell checking, search suggestions, deduplication, and fuzzy matching. The standard approach uses string distance metrics — Levenshtein distance, Jaro-Winkler similarity, or cosine similarity on n-grams — to rank candidates by similarity. Python's difflib and the fuzzywuzzy/rapidfuzz libraries make this straightforward.

Method 1: difflib.get_close_matches (Built-in)

Python's standard library includes difflib for sequence matching:

python
1from difflib import get_close_matches, SequenceMatcher
2
3# Find closest matches from a list
4words = ['apple', 'application', 'apply', 'banana', 'grape', 'pineapple']
5
6matches = get_close_matches('aple', words, n=3, cutoff=0.6)
7print(matches)  # ['apple', 'apply', 'maple'] — ranked by similarity
8
9# Get similarity ratio between two strings
10ratio = SequenceMatcher(None, 'apple', 'aple').ratio()
11print(f"Similarity: {ratio:.3f}")  # 0.889

SequenceMatcher uses the Ratcliff/Obershelp algorithm, which finds the longest common subsequence.

Method 2: Levenshtein Distance

Levenshtein distance counts the minimum number of single-character edits (insertions, deletions, substitutions) to transform one string into another:

python
1# Using python-Levenshtein or rapidfuzz
2from rapidfuzz.distance import Levenshtein
3
4# Distance (lower = more similar)
5dist = Levenshtein.distance('kitten', 'sitting')
6print(f"Distance: {dist}")  # 3
7
8# Normalized similarity (0 to 1)
9sim = Levenshtein.normalized_similarity('kitten', 'sitting')
10print(f"Similarity: {sim:.3f}")  # 0.571

Manual Implementation

python
1def levenshtein_distance(s1, s2):
2    m, n = len(s1), len(s2)
3    dp = [[0] * (n + 1) for _ in range(m + 1)]
4
5    for i in range(m + 1):
6        dp[i][0] = i
7    for j in range(n + 1):
8        dp[0][j] = j
9
10    for i in range(1, m + 1):
11        for j in range(1, n + 1):
12            if s1[i-1] == s2[j-1]:
13                dp[i][j] = dp[i-1][j-1]
14            else:
15                dp[i][j] = 1 + min(dp[i-1][j],      # deletion
16                                    dp[i][j-1],      # insertion
17                                    dp[i-1][j-1])    # substitution
18    return dp[m][n]
19
20print(levenshtein_distance('kitten', 'sitting'))  # 3

Method 3: FuzzyWuzzy / RapidFuzz

rapidfuzz (a faster C-based replacement for fuzzywuzzy) provides several fuzzy matching strategies:

python
1from rapidfuzz import fuzz, process
2
3# Simple ratio
4print(fuzz.ratio('New York', 'new york'))           # 82
5print(fuzz.ratio('New York', 'New York City'))       # 82
6
7# Partial ratio (best substring match)
8print(fuzz.partial_ratio('New York', 'New York City'))  # 100
9
10# Token sort (order-independent)
11print(fuzz.token_sort_ratio('John Smith', 'Smith John'))  # 100
12
13# Token set (handles duplicates and subsets)
14print(fuzz.token_set_ratio('Los Angeles CA', 'CA Los Angeles California'))  # 100

Find Best Match from a List

python
1choices = ['New York', 'Los Angeles', 'Chicago', 'Houston', 'Phoenix']
2
3# Best single match
4best = process.extractOne('new yrok', choices)
5print(best)  # ('New York', 90, 0)  — (match, score, index)
6
7# Top N matches
8top3 = process.extract('chcago', choices, limit=3)
9print(top3)
10# [('Chicago', 91, 2), ('New York', 18, 0), ('Phoenix', 14, 4)]

Method 4: Jaro-Winkler Similarity

Optimized for short strings like names — gives bonus weight to matching prefixes:

python
1from rapidfuzz.distance import JaroWinkler
2
3sim = JaroWinkler.similarity('MARTHA', 'MARHTA')
4print(f"Similarity: {sim:.3f}")  # 0.961
5
6sim2 = JaroWinkler.similarity('DIXON', 'DICKSONX')
7print(f"Similarity: {sim2:.3f}")  # 0.813

Method 5: Cosine Similarity on N-grams

For longer texts, convert strings to n-gram vectors and compute cosine similarity:

python
1from sklearn.feature_extraction.text import TfidfVectorizer
2from sklearn.metrics.pairwise import cosine_similarity
3
4documents = [
5    'machine learning algorithms',
6    'deep learning neural networks',
7    'statistical machine learning',
8    'cooking Italian pasta recipes',
9]
10
11query = 'machine learning techniques'
12
13vectorizer = TfidfVectorizer(analyzer='char_wb', ngram_range=(2, 3))
14tfidf = vectorizer.fit_transform(documents + [query])
15
16# Similarity of query against all documents
17similarities = cosine_similarity(tfidf[-1:], tfidf[:-1]).flatten()
18
19for doc, score in sorted(zip(documents, similarities), key=lambda x: -x[1]):
20    print(f"{score:.3f}: {doc}")
21# 0.812: machine learning algorithms
22# 0.645: statistical machine learning
23# 0.234: deep learning neural networks
24# 0.000: cooking Italian pasta recipes

Comparison of Methods

MethodBest ForCase SensitiveSpeed
SequenceMatcherGeneral purposeYesModerate
LevenshteinShort strings, spell checkYesFast
Jaro-WinklerNames, short stringsYesFast
fuzz.token_sort_ratioReordered wordsNoFast
fuzz.partial_ratioSubstring matchingNoFast
Cosine (TF-IDF)Long texts, documentsConfigurableModerate
python
1from rapidfuzz import process, fuzz
2
3# Product catalog
4products = [
5    'iPhone 15 Pro Max',
6    'Samsung Galaxy S24 Ultra',
7    'Google Pixel 8 Pro',
8    'OnePlus 12',
9    'Sony Xperia 1 V',
10]
11
12def fuzzy_search(query, choices, threshold=60):
13    results = process.extract(query, choices, scorer=fuzz.token_set_ratio, limit=5)
14    return [(match, score) for match, score, _ in results if score >= threshold]
15
16print(fuzzy_search('iphone pro'))
17# [('iPhone 15 Pro Max', 90)]
18
19print(fuzzy_search('galaxy'))
20# [('Samsung Galaxy S24 Ultra', 90)]
21
22print(fuzzy_search('pixel'))
23# [('Google Pixel 8 Pro', 90)]

Common Pitfalls

  • Case sensitivity: Most distance metrics are case-sensitive. 'Apple' and 'apple' have distance 1. Normalize to lowercase before comparing unless case matters.
  • Whitespace and punctuation: 'New York' and 'NewYork' have distance 1, but 'New York' (double space) adds another. Strip and normalize whitespace before comparing.
  • Performance at scale: Computing distances against millions of candidates is O(n * m) per pair. Use indexing techniques (BK-trees, locality-sensitive hashing) or rapidfuzz.process.cdist for bulk comparisons.
  • Choosing the right metric: Levenshtein works for typos; Jaro-Winkler works for names; token-based ratios work for reordered words; cosine similarity works for documents. No single metric is best for all cases.
  • Threshold tuning: A cutoff of 80 works for many applications, but the optimal threshold depends on your data. Too low gives false positives; too high misses valid matches. Evaluate on labeled examples.

Summary

  • Use difflib.get_close_matches for simple built-in fuzzy matching
  • Use rapidfuzz (or fuzzywuzzy) for production fuzzy matching with multiple scoring strategies
  • Use Levenshtein distance for edit-based similarity (typos, misspellings)
  • Use Jaro-Winkler for name matching and short strings
  • Use TF-IDF cosine similarity for document-level text similarity
  • Always normalize case and whitespace before comparing
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.