Ruby每周一测 - 容易记的电话号码

Ruby每周一测 - Ruby Quiz 是Ruby Talk邮件列表上的一个持续了很长时间活动，每周有一个小题目被提出来，然后大家进行解答讨论。Amazon上还有相关的书： Best of Ruby Quiz。我尝试挑选其中的一些题目进行翻译，做一个每周一测系列，欢迎大家参与讨论。

-----题目分割线-----

以前在国外的影视或者广告中看到出现含字母的电话号码，比如1-800-PICK-UPS (美国UPS快递号码)，心中不免有些疑惑：难道国外的电话是可以拨字母的？后来请教国外朋友，才明白这个疑问有点傻有点天真  看一下常见的电话键盘：

每个数字旁边都有3个或者4个字母对应，那么上面这个电话号码其实就是1-800-7425-877，这样就把一个难记的电话号码通过简单的单词记住了。这周的题目就是完成下面这个方法，通过查找字典把输入的数字变成可能的字母输出，比如输入8737829得到USE-RUBY，为了编程简单，这里假设字典文件已经被读取到一个words的数组里面作为参数传递：

def build_word_list(number, words = %w{USE RUBY} , mapping = %w{ABC DEF GHI JKL MNO PQRS TUV WXYZ}, delimeter = "-")
  
end

-----解答分割线-----
原题和一些解法在这里：http://rubyquiz.com/quiz20.html

来一个Scala版的...基本上是拼凑而成的,对Scala的API太不熟悉了
BTW: 我给的代码与LZ的要求稍有不同,PhoneNumber构造函数的参数mapping必须是一个长度为10的字符串数组,代表0~9对应的字母

import java.util.HashMap

object Main2 extends Application{
	var pn =new PhoneNumber(Array("USE","RUBY"),Array("","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"),"-")
	pn.buildWordList(8737829).foreach(s=>println(s))
}

class PhoneNumber(words:Array[String],mapping:Array[String],delimeter:String){
	
	def buildWordList(phoneNum:Int):Array[String] = 
	    build((phoneNum+"").toCharArray,0,-1,Array[String]("")).map(s=>s.substring(0,s.length()-1))
	
	private def build(array:Array[Char],start:Int,preNum:Int,exisit:Array[String]):Array[String]={
		if(start>=array.length) return if(preNum== -1) exisit else Array()
		var newNum =if(preNum == -1) array(start)-'0' else preNum*10 +array(start)-'0'
		var ws =map.get(newNum)
		var add =if(ws!=null) build(array,start+1,-1,exisit.flatMap(s=>ws.map(w=>s+w+delimeter))) else Array[String]()
		Array.concat(add,build(array,start+1,newNum,exisit))
	}
	
	private val map =new HashMap[Int,Array[String]]
	words.foreach(str=>{
		var num =0
		str.foreach(c=>num =num*10+charToNum(c))
		var array =map.get(num)
		if(array==null) array =Array[String]()
		array =Array.concat(array,Array(str))
		map.put(num,array)
	})
	private def charToNum(c:Char):Int={
		var num =0
		mapping.foreach(str=>if(str.indexOf(c)>=0)return num;else num=num+1)
		-1
	}
}

另外,按LZ"通过查找字典把输入的数字变成可能的字母输出"的意思
我的上面代码得到的结果字符串中不会包含数字,也就是某些号码会无解
但我看了下原题,貌似是可以包含数字的,譬如号码"1-800-PICK-UPS "应该可以以"1800-PICK-UPS "形式作为一个解.
我写了个容许数字出现的代码,不过稍微复杂些.

贴一个python版本的，惭愧，弄了一晚上

#-*- coding: utf-8 -*-
#!/usr/bin/env python
from __future__ import with_statement

button_mapping = {
    'A' : 2, 'B' : 2, 'C' : 2,
    'D' : 3, 'E' : 3, 'F' : 3,
    'G' : 4, 'H' : 4, 'I' : 4,
    'J' : 5, 'K' : 5, 'L' : 5,
    'M' : 6, 'N' : 6, 'O' : 6,
    'P' : 7, 'Q' : 7, 'R' : 7, 'S' : 7,
    'T' : 8, 'U' : 8, 'V' : 8,
    'W' : 9, 'X' : 9, 'Y' : 9, 'Z' : 9,
}


"""
{ word_signature:word }
"""
signatures = {}

def suffeient(word):
    """
    remove empty and un-mapped strings 
    """
    if not word:
        return False
    if len(word) >= 2 and word[-2] == "\'":
        return False
    for c in word:
        if not (c.upper() in button_mapping.keys()):
            return False
    return True

def make_signature(word, sig_dict):
    #def action_maker(seq):
    #    return lambda c: seq.append(c)
    sig_tmp = []
    #f = action_maker(sig_tmp)
    [ sig_tmp.append(str(button_mapping[c])) for c in [c.upper() for c in word] ]
    sig_dict[''.join(sig_tmp)] = word


def make_signatures(words):
    global signatures
    [ make_signature(word, signatures) for word in words if suffeient(word) ]
    
   
def build_word_list(number, words_dict, indent=0):
    """
    Brief introduction of the algorithm:
    
    Find all of the signatures that are contained in the number in the signature dict
    Sort the matched keys in decend order
    For each of the matched element:
        divide the element into 3 parts: header, matched, reminder
        call the build_word_list recursively to find the possible matched word
        for the header and reminder parts, respectively
        examine the result and return
        
    There might be more than one word having the same signature, it depends the
    signature-building algorithm and the signature storage's data structure. In
    this solution the words having the duplicated signatures are omitted to
    reduce the complexity of the implementation; this simplification should not
    (um..., maybe not:-)) affect the correctness of the algorithm.
    """
    
    def compose_result(header, matched, reminder):
        ret = "%s-%s-%s" % (header, matched, reminder)
        if ret[0] == '-':
            return ret[1:]
        elif ret[-1] == '-':
            return ret[0:-1]
        else:
            return ret
    
    #print '%sinput:%s' % (indent * '.', number )
    if not number:
        return True, number
    if number in words_dict.keys():
        #print '%smatches:%s' % ( indent * '.', words_dict[number] )
        return True, number
    else:
        possible_matches = [num for num in words_dict.keys() if num in number]
        possible_matches.sort(lambda a,b:len(a) < len(b) and 1 or -1)
        #print '%spossible_matches: %s' % (indent * '.', [ (word, words_dict[word]) for word in possible_matches ])
        
        for matched in possible_matches:
            header_num, matched_num, reminder_num = number.partition(matched)
            #print "header_num:%s, matched_num:%s, reminder_num:%s" % (header_num, matched_num, reminder_num)
            header_matched, header_word = build_word_list(header_num,
                                                          words_dict, indent + 1)
            reminder_matched, reminder_word = build_word_list(reminder_num,
                                                              words_dict, indent + 1)
            if header_matched and reminder_matched:
                return True, compose_result(header_word, matched, reminder_word)
            elif header_matched and not reminder_matched:
                return False, compose_result(header_word, matched, reminder_num)
            elif not header_matched and reminder_matched:
                return False, compose_result(header_num, matched, reminder_word)
            elif not header_matched and not reminder_matched:
                return False, compose_result(header_num, matched, reminder_num)
            else:
                pass
        return False, number
    
def output(build_result):
    global signatures
    ret = ""
    grouped_result = build_result[1].split('-')
    #print "build result %s, %s:" % build_result
    for group in grouped_result:
        if signatures.has_key(group):
            ret = ret + "-" + signatures[group]
        else:
            ret = ret + "-" + group
    return ret[1:]

def input(number):
    return ''.join(str(number).split('-'))


if __name__ == '__main__':
    with file('words') as f:
        trimed = [ line[0:-1] for line in f ]
        make_signatures(trimed)
        
        word_list = build_word_list('118737829', signatures)
        print word_list and output(word_list) or "None"
        
        word_list = build_word_list('7425877', signatures)
        print word_list and output(word_list) or "None"
        
        word_list = build_word_list('74258777425877', signatures)
        print word_list and output(word_list) or "None"
        
        word_list = build_word_list(input('1-800-7425-877'), signatures)
        print word_list and output(word_list) or "None"

还不完善，先贴上来吧。

def word_to_number(word,mapping)
  number_str=""
  word.length.times do |i|
    c=word[i..i]
    mapping.each_with_index do |abc,index|
      if abc.include?(c)
        number_str<<(index+2).to_s
      end
    end
  end
  number_str.to_i
end

def build_number_list(words,mapping)
  number_list={}
  words.each do |word|
    number_list[word_to_number(word,mapping)]=word
  end
  return number_list.sort
end

def build_word_list(number, words = %w{USE RUBY} , mapping = %w{ABC DEF GHI JKL MNO PQRS TUV WXYZ}, delimeter = "-")
  number_list=build_number_list(words,mapping)
  number_list.reverse_each do |num_word|
    num=num_word[0].to_s
    word=num_word[1]
    locate=number.index(num)
    number[locate..locate+num.length-1]=word if locate>=0
    number.insert(locate,delimeter) if locate>0
  end
  return number
end

p build_word_list("8737829")

看了下你的代码(偶从没学过Ruby,说错了勿怪:-)),
按题目中,很可能两个不同的单词对应一个相同的数字(因为每个数字可能对应几个字母)
就是说word_to_number方法对两个word会返回同一个值,那你这样会不会将某些word丢掉了?然后造成结果变少?
PS:偶不清楚Ruby中number_list={}是声明了个什么东东,但貌似无论是数组还是Map都会有问题

换了一种算法,写的比之前的好看一点:-)

import scala.collection.mutable.HashMap

object MainX extends Application{
	var pn =new PhoneBeta(Array("USE","RUBY"),Array("","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"),"-")
	pn.buildWordList(8737829).foreach(word=>println(word))
}

class PhoneBeta(words:Array[String],mapping:Array[String],delimeter:String){
	
	def buildWordList(num:Int) =build(num+"")
	
	def build(num:String):Array[String]={
		var result = map.getOrElse(num,Array[String]())
		for(i <- 1 until num.length()){
			var left =build(num.slice(0,i))
			var right =build(num.slice(i,num.length()))
			var add  =left.flatMap(lt=>right.map(rt=>lt+delimeter+rt))
			result =Array.concat(result,add)
		}
		result
	}
	private val map =new HashMap[String,Array[String]]
	words.foreach(word=>{
		var str =""
		word.foreach(c=>{
			str += mapping.findIndexOf(m =>m.indexOf(c)>=0)
		})
		var arr =map.getOrElse(str,Array[String]())
		arr =Array.concat(arr,Array(word))
		map.put(str,arr)
	})
}

这个算法的时间复杂度是指数级的O(2^n),不过只要简单的修改一下,加上动态规划就可以将时间复杂度降到三次方级O(n^3),这里n指电话号码的长度,并忽略了构造HashMap的时间.当单词表比较大时,这个时间不能忽略.

是会丢掉的。不过这个应该算是题目的问题吧。

如果两个单词的对应数字相同，那么在给定的电话号码，换算的过程中，我该如何选择单词呢？

总不会是根据英语的含义吧。。

如果一串数字有多个解的话，是返回一个Array