Valid Word Abbreviation - Practice Coding Problems

Valid Word Abbreviation - Problem

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

"s10n" ("s ubstitutio n")
"sub4u4" ("sub stit u tion")
"12" ("substitution")
"su3i1u2on" ("su bst i t u ti on")
"substitution" (no substrings replaced)

The following are not valid abbreviations:

"s55n" (the replaced substrings are adjacent)
"s010n" (has leading zeros)
"s0ubstitution" (replaces an empty substring)

Given a string word and an abbreviation abbr, return true if the string matches the given abbreviation, false otherwise.

Input & Output

Example 1 — Valid Abbreviation

$ Input: word = "internationalization", abbr = "i12iz4n"

› Output: true

💡 Note: The abbreviation "i12iz4n" represents "i" + 12 characters + "iz" + 4 characters + "n" = "internationalization"

Example 2 — Invalid Leading Zero

$ Input: word = "apple", abbr = "a2e"

› Output: false

💡 Note: The abbreviation "a2e" would be "a" + 2 characters + "e" = "apple" but this doesn't match because we need "a" + "pp" + "e"

Example 3 — Leading Zero Invalid

$ Input: word = "substitution", abbr = "s010n"

› Output: false

💡 Note: The abbreviation contains "010" which has leading zeros, making it invalid

Constraints

1 ≤ word.length ≤ 20
1 ≤ abbr.length ≤ 10
word consists of only lowercase English letters
abbr consists of lowercase English letters and digits

Visualization

Tap to expand

Understanding the Visualization

Input

word="internationalization", abbr="i12iz4n"

Process

Match characters and parse numbers to skip sections

Output

Return true if abbreviation is valid for the word

Key Takeaway

🎯 Key Insight: Numbers in abbreviations tell us exactly how many characters to skip in the original word

Asked in

G Google 45 f Facebook 32 M Microsoft 28

The key insight is to use two pointers to traverse both strings simultaneously. When encountering digits in the abbreviation, parse the complete number and skip that many characters in the original word. Best approach is two pointers with Time: O(n+m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Expansions	O(k^n)	O(k^n)	Generate all possible expansions of the abbreviation and check if any match the word
Two Pointers - Character by Character Matching	O(n + m)	O(1)	Use two pointers to traverse both strings, parsing numbers in abbreviation

Brute Force - Generate All Expansions — Algorithm Steps

Generate all possible character combinations for each number
Check each expansion against the original word
Return true if any expansion matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Numbers

Find each number in abbreviation like '10' in 's10n'

Generate Expansions

Create all possible character combinations for each number

Check Matches

Compare each expansion with original word

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

bool solution(char* word, char* abbr) {
    // Implementing efficient approach instead of true brute force
    int i = 0, j = 0;
    int word_len = strlen(word);
    int abbr_len = strlen(abbr);
    
    while (i < word_len && j < abbr_len) {
        if (isdigit(abbr[j])) {
            if (abbr[j] == '0') {
                return false; // Leading zero
            }
            
            int num = 0;
            while (j < abbr_len && isdigit(abbr[j])) {
                num = num * 10 + (abbr[j] - '0');
                j++;
            }
            
            i += num;
        } else {
            if (word[i] != abbr[j]) {
                return false;
            }
            i++;
            j++;
        }
    }
    
    return i == word_len && j == abbr_len;
}

int main() {
    char word[1000], abbr[1000];
    
    fgets(word, sizeof(word), stdin);
    fgets(abbr, sizeof(abbr), stdin);
    
    // Remove newlines
    word[strcspn(word, "\n")] = 0;
    abbr[strcspn(abbr, "\n")] = 0;
    
    bool result = solution(word, abbr);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

Where k is average number length and n is count of numbers - exponential combinations

✓ Linear Growth

Space Complexity

O(k^n)

Need to store all possible expansions in memory

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Expansions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler