难度: Hard
给定一个整数，打印该整数的英文描述。
示例 1:
输入: 123 输出: "One Hundred Twenty Three"
示例 2:
输入: 12345 输出: "Twelve Thousand Three Hundred Forty Five"
示例 3:
输入: 1234567 输出: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
示例 4:
输入: 1234567891 输出: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"
注意：本题与 273 题相同：https://leetcode-cn.com/problems/integer-to-english-words/
运行时间: 31 ms
内存: 16.2 MB
class Solution:
def numberToWords(self, num: int) -> str:
num_dict={"1":"One","2":"Two","3":"Three","4":"Four","5":"Five",'6':"Six",'7':"Seven",'8':"Eight",'9':"Nine",'10':"Ten",'11':"Eleven",'12':"Twelve",'13':"Thirteen",'14':"Fourteen",'15':"Fifteen",'16':"Sixteen",'17':"Seventeen",'18':"Eighteen",'19':"Nineteen",'20':"Twenty",'30':"Thirty",'40':"Forty",'50':"Fifty",'60':"Sixty",'70':"Seventy",'80':"Eighty",'90':"Ninety"}
num_count={1:"Thousand",2:"Million",3:"Billion",4:"Trillion"}
if num==0:
return 'Zero'
count=0
output=[]
num_str=str(num)
n=len(num_str)
str_list=[]
index=len(num_str)-1
while index>=0:
temp=[]
if index >=2:
temp.append(num_str[index-2])
if index >=1:
temp.append(num_str[index-1])
temp.append(num_str[index])
str_list.append(''.join(temp))
index=index-3
for triplet in str_list:
temp=''
if len(triplet)==3:
if triplet[0]!='0': # xxx
temp += num_dict[triplet[0]] + ' Hundred '
if triplet[1]!='0': #xxx
if triplet[1]+triplet[2] in num_dict:
temp+=num_dict[triplet[1]+triplet[2]]
else:
temp+=num_dict[triplet[1]+'0'] +' ' + num_dict[triplet[2]]
else:# x0x
if triplet[2]!='0':
temp+=num_dict[triplet[2]]
else:# x00
temp=temp[:-1]
else: # tri is 0xx
if triplet[1]!='0':
if triplet[1]+triplet[2] in num_dict:
temp+=num_dict[triplet[1]+triplet[2]]
else:
temp+=num_dict[triplet[1]+'0'] + ' ' + num_dict[triplet[2]]
else:# 00x
if triplet[2]!='0':# 00x
temp+=num_dict[triplet[2]]
else:# 000
temp+='Zero'
if len(triplet)<=2:
if triplet in num_dict:
temp+=num_dict[triplet]
else:
temp += num_dict[triplet[0] + '0'] +' '+ num_dict[triplet[1]]
output.append(temp)
result=[output[0]]
for i in range(len(output)-1):
result.append(num_count[i+1])
result.append(output[i+1])
result.reverse()
index=0
while index<len(result):
if result[index]=="Zero":
if index==len(result)-1:
result.pop(index)
else:
result.pop(index)
result.pop(index)
else:
index+=1
return ' '.join(result)
The solution converts a given integer to its English words representation. It uses a dictionary to map numbers to their English counterparts for single digits, two digits, and multiples of ten. The algorithm handles the integer in chunks of three digits, corresponding to the place values like Thousand, Million, etc. These chunks are processed from right to left, adjusting for place value. Special attention is given to numbers like '100' or '110' where 'Zero' needs to be managed correctly to avoid incorrect outputs like 'Zero Hundred'. The final English representation is then constructed by reversing the order of processed chunks and concatenating them with appropriate place values.
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def numberToWords(self, num: int) -> str:
# Dictionary for number to word conversion
num_dict = {'1': 'One', '2': 'Two', '3': 'Three', '4': 'Four', '5': 'Five', '6': 'Six', '7': 'Seven', '8': 'Eight', '9': 'Nine', '10': 'Ten', '11': 'Eleven', '12': 'Twelve', '13': 'Thirteen', '14': 'Fourteen', '15': 'Fifteen', '16': 'Sixteen', '17': 'Seventeen', '18': 'Eighteen', '19': 'Nineteen', '20': 'Twenty', '30': 'Thirty', '40': 'Forty', '50': 'Fifty', '60': 'Sixty', '70': 'Seventy', '80': 'Eighty', '90': 'Ninety'}
# Place value names by chunk index
num_count = {1: 'Thousand', 2: 'Million', 3: 'Billion', 4: 'Trillion'}
# Handle zero explicitly
if num == 0:
return 'Zero'
# General case
count = 0
output = []
num_str = str(num)
n = len(num_str)
str_list = []
index = len(num_str) - 1
while index >= 0:
temp = []
if index >= 2:
temp.append(num_str[index - 2])
if index >= 1:
temp.append(num_str[index - 1])
temp.append(num_str[index])
str_list.append(''.join(temp))
index -= 3
for triplet in str_list:
temp = ''
if len(triplet) == 3:
if triplet[0] != '0':
temp += num_dict[triplet[0]] + ' Hundred '
if triplet[1] != '0':
if triplet[1] + triplet[2] in num_dict:
temp += num_dict[triplet[1] + triplet[2]]
else:
temp += num_dict[triplet[1] + '0'] + ' ' + num_dict[triplet[2]]
else:
if triplet[2] != '0':
temp += num_dict[triplet[2]]
else:
if triplet[1] != '0':
if triplet[1] + triplet[2] in num_dict:
temp += num_dict[triplet[1] + triplet[2]]
else:
temp += num_dict[triplet[1] + '0'] + ' ' + num_dict[triplet[2]]
else:
if triplet[2] != '0':
temp += num_dict[triplet[2]]
if len(triplet) <= 2:
if triplet in num_dict:
temp += num_dict[triplet]
else:
temp += num_dict[triplet[0] + '0'] + ' ' + num_dict[triplet[1]]
output.append(temp)
result = [output[0]]
for i in range(len(output) - 1):
result.append(num_count[i + 1])
result.append(output[i + 1])
result.reverse()
index = 0
while index < len(result):
if result[index] == 'Zero':
if index == len(result) - 1:
result.pop(index)
else:
result.pop(index)
result.pop(index)
else:
index += 1
return ' '.join(result)
当输入的整数为零时，算法直接返回'Zero'，这是通过代码中的特殊条件判断实现的 (`if num == 0: return 'Zero'`)。对于前导零的情况，由于数字是以字符串形式处理，且在处理每三位数时，会检查每一位的值，只有当非零时才会添加相应的英文单词。因此，前导零自然地被忽略，不影响最终输出。
在处理每三位数时，算法检查每一位的值。如果百位为'0'，则不会添加'Hundred'及其前的数字单词；如果十位为'0'，则会跳过'Zero'，直接处理个位数。例如，对于'001'，算法只识别并输出'One'；对于'010'，仅输出'Ten'。这种处理方式确保不会出现多余的'Zero'或'Zero Hundred'。
对于'105'这样的数字，算法首先识别出百位和个位（'1'和'5'），忽略中间的零。具体来说，算法会首先将'1'转换为'One Hundred'。然后，由于十位是'0'，算法不会输出'Ten'或'Zero'，而是直接处理个位的'5'，将其转换成'Five'。最终组合成'One Hundred Five'。这个逻辑避免了在输出中包含不必要的'Zero'。