Welcome to Subscribe On Youtube

3758. Convert Number Words to Digits 🔒

Description

You are given a string s consisting of lowercase English letters. s may contain valid concatenated English words representing the digits 0 to 9, without spaces.

Your task is to extract each valid number word in order and convert it to its corresponding digit, producing a string of digits.

Parse s from left to right. At each position:

• If a valid number word starts at the current position, append its corresponding digit to the result and advance by the length of that word.
• Otherwise, skip exactly one character and continue parsing.

Return the resulting digit string. If no number words are found, return an empty string.

 

Example 1:

Input: s = "onefourthree"

Output: "143"

Explanation:

• Parsing from left to right, extract the valid number words "one", "four", "three".
• These map to digits 1, 4, 3. Thus, the final result is "143".

Example 2:

Input: s = "ninexsix"

Output: "96"

Explanation:

• The substring "nine" is a valid number word and maps to 9.
• The character "x" does not match any valid number word prefix and is skipped.
• Then, the substring "six" is a valid number word and maps to 6, so the final result is "96".

Example 3:

Input: s = "zeero"

Output: ""

Explanation:

• No substring forms a valid number word during left-to-right parsing.
• All characters are skipped and incomplete fragments are ignored, so the result is an empty string.

Example 4:

Input: s = "tw"

Output: ""

Explanation:

• No substring forms a valid number word during left-to-right parsing.
• All characters are skipped and incomplete fragments are ignored, so the result is an empty string.

 

Constraints:

• 1 <= s.length <= 105
• s contains only lowercase English letters.

Solutions

Solution 1: Enumeration

We first establish a mapping relationship between number words and their corresponding digits, recorded in array $d$, where $d[i]$ represents the word corresponding to digit $i$.

Then we traverse the string $s$ from left to right. For each position $i$, we enumerate the number words $d[j]$ in order and check whether the substring starting from position $i$ matches $d[j]$. If a match is found, we add digit $j$ to the result and move position $i$ forward by $|d[j]|$ positions. Otherwise, we move position $i$ forward by 1 position.

We repeat this process until we have traversed the entire string $s$. Finally, we concatenate the digits in the result into a string and return it.

The time complexity is $O(n \times |d|)$ and the space complexity is $O(|d|)$, where $n$ is the length of string $s$ and $|d|$ is the number of digit words.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public String convertNumber(String s) {
          String[] d
              = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
          int n = s.length();
          StringBuilder ans = new StringBuilder();
          for (int i = 0; i < n; ++i) {
              for (int j = 0; j < d.length; ++j) {
                  String t = d[j];
                  int m = t.length();
                  if (i + m <= n && s.substring(i, i + m).equals(t)) {
                      ans.append(j);
                      i += m - 1;
                      break;
                  }
              }
          }
          return ans.toString();
      }
  }
  
  

• class Solution {
  public:
      string convertNumber(string s) {
          vector<string> d = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
          int n = s.length();
          string ans;
          for (int i = 0; i < n; ++i) {
              for (int j = 0; j < d.size(); ++j) {
                  string t = d[j];
                  int m = t.length();
                  if (i + m <= n && s.substr(i, m) == t) {
                      ans += to_string(j);
                      i += m - 1;
                      break;
                  }
              }
          }
          return ans;
      }
  };
  
  

• class Solution:
      def convertNumber(self, s: str) -> str:
          d = [
              "zero",
              "one",
              "two",
              "three",
              "four",
              "five",
              "six",
              "seven",
              "eight",
              "nine",
          ]
          i, n = 0, len(s)
          ans = []
          while i < n:
              for j, t in enumerate(d):
                  m = len(t)
                  if i + m <= n and s[i : i + m] == t:
                      ans.append(str(j))
                      i += m - 1
                      break
              i += 1
          return "".join(ans)
  
  

• func convertNumber(s string) string {
  	d := []string{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}
  	n := len(s)
  	var ans strings.Builder
  	for i := 0; i < n; i++ {
  		for j, t := range d {
  			m := len(t)
  			if i+m <= n && s[i:i+m] == t {
  				ans.WriteString(strconv.Itoa(j))
  				i += m - 1
  				break
  			}
  		}
  	}
  	return ans.String()
  }
  
  

• function convertNumber(s: string): string {
      const d: string[] = [
          'zero',
          'one',
          'two',
          'three',
          'four',
          'five',
          'six',
          'seven',
          'eight',
          'nine',
      ];
      const n = s.length;
      const ans: string[] = [];
      for (let i = 0; i < n; ++i) {
          for (let j = 0; j < d.length; ++j) {
              const t = d[j];
              const m = t.length;
              if (i + m <= n && s.substring(i, i + m) === t) {
                  ans.push(j.toString());
                  i += m - 1;
                  break;
              }
          }
      }
      return ans.join('');
  }
  
  

All Problems

All Solutions