一个精妙的解决方案并非对于所有语言都是最优解

一个精妙的解决方案并非对于所有语言都是最优解

今天无意间看到一篇文章(http://www.vaikan.com/google-interviewing-story/)，看到里面有道面试题的算法挺有意思的。问题是这样的：假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？比如，如果是下面两个字符串：String 1: ABCDEFGHLMNOPQrsstring 2: DCGSRQPOM答案是true，所有在string2里的字母string1也都有。如果是下面两个字符串：String 1: ABCDEFGHLMNOPQRSString 2: DCGSRQPOZ

所以，第一个整数失真在：alert(9007199254740992 == 9007199254740993);//true

var result = 1;var numObject = {    'A': 2,    'B': 3,    'C': 5,    'D': 7,    'E': 11,    'F': 13,    'G': 17,    'H': 19,    'I': 23,    'J': 29,    'K': 31,    'L': 37,    'M': 41,    'N': 43,    'O': 47,    'P': 53,    'Q': 59,    'R': 61,    'S': 67,    'T': 71,    'U': 73,    'V': 79,    'W': 83,    'X': 89,    'Y': 97,    'Z': 101};var init = function() {     compareString('ABCDEFGHLMNOPQRS', 'DBGSRQPOZ');};var compareString = function(str1, str2) {    var i,          j,          length;    //长的字符串每个字母相乘    for (i = 0, j = 1, length = str1.length; i < length; i++) {        result *= numObject[str1.substr(i, 1)];    }    //结果除以短的字符串的每个字母    for (i = 0, length = str2.length; i < length; i++) {          if (result % numObject[str2.substr(i, 1)] !== 0) {               console.log("str2"中的第" + (i + 1) + "个字母不存在str1中");               break;          } else {               result /= numObject[str2.substr(i, 1)];          }              }};init();

var resultObject = {    'result1': 1};

var compareString = function(str1, str2) {    var i,        j,        flag,        length;    //长的字符串每个字母相乘    for (i = 0, j = 1, length = str1.length; i < length; i++) {        //相乘结果大于2的53次方时，设置新的属性值result+j来统计结果        if (resultObject['result' + j] * numObject[str1.substr(i, 1)] > Math.pow(2, 53)) {            j++;            resultObject['result' + j] = 1;        }        resultObject['result' + j] *= numObject[str1.substr(i, 1)];    }    //结果除以短的字符串的每个字母    for (i = 0, length = str2.length; i < length; i++) {        flag = 0;        for (var z in resultObject) {            if (resultObject[z] % numObject[str2.substr(i, 1)] === 0) {                flag = 0;                break;            } else {                flag = 1;            }        }        if (flag == 1) {            console.log("str2中的第" + (i + 1) + "个字母不存在str1中");            break;        } else if (flag == 0 && i == length - 1) {            console.log("str2中的字母str1均存在");        }    }};

这样理论上是没问题了，但有个限制条件，str1的长度必须大于等于str2。

题目是查出所有小字符串里的字母在大字符串里都有，显然当用户如果先输入小字符串，再输入大字符串的话，结果就不尽如人意了。

所以，我们再对compareString方法做下优化，长字符串每个字母相乘前面部分做个判断，str1长度小于str2时，两个字符串互换值

var i,    j,    flag,    length,    strLong = 1, //默认str1为长字符串    strShort = 2, //默认str2为短字符串    strArray = [str1, str2];//当str1长度小于str2时if (str1.length < str2.length) {    strLong = 2;    strShort = 1;    str1 = strArray[1];    str2 = strArray[0];}

同时，输出结果那里更改如下：

if (flag == 1) {    console.log("str" + strShort + "中的第" + (i + 1) + "个字母不存在str" + strLong + "中");    break;} else if (flag == 0 && i == length - 1) {    console.log("str" + strShort + "中的字母str" + strLong + "均存在");}

这样，无论用户先输入长字符串或短字符串，就都能正常进行判断了。

所以，其实在JS中，这种算法并不是最优算法。

在JS中，还是把长字符串的每个字母存在到一个对象中作为它的属性，再轮询短的字符串，如果出现对象中没有的属性，则说明出现了长字符串中所没有的字母。

代码如下：

var init = function() {    compareString('ABCDEFGHLMNOPQRS', 'DBGSRQPOZ');};var compareString = function(str1, str2) {    var i,        flag,        length,        strLong = 1, //默认str1为长字符串        strShort = 2, //默认str2为短字符串        numObject = {};        strArray = [str1, str2];    //当str1长度小于str2时    if (str1.length < str2.length) {        strLong = 2;        strShort = 1;        str1 = strArray[1];        str2 = strArray[0];    }    //将字符串str1中的每个字母添加到numObject中作为它的属性    for (i = 0, length = str1.length; i < length; i++) {        //如果同一个字母出现多次，只对第一次添加属性        if (!numObject[str1.substr(i, 1)]) {            numObject[str1.substr(i, 1)] = 1;        }    }    for (i = 0, length = str2.length; i < length; i++) {        //如果str2中同一个字母出现多次，只对第一次进行比较        if (numObject[str2.substr(i, 1)] === 0) {            continue;        }        //如果numObject中不存在这个属性，说明这个字母str1中没有        if (!numObject[str2.substr(i, 1)]) {            console.log("str" + strShort + "中的第" + (i + 1) + "个字母不存在str" + strLong + "中");            return;        } else {            //已经出现过一次了，赋值为0            numObject[str2.substr(i, 1)] = 0;        }    }    console.log("str" + strShort + "中的字母str" + strLong + "均存在");};init();

的确，在实践中，还是最后这种解决方法更加通用。无论哪一种语言都是。因为他更加通俗易懂，也不需要跟一些大数乘除打交道。

只是最近看到这个文章觉得用素数来解决这个问题确实很有趣，也是我之前从未想过的。虽然这个方法对于JS并非最优方案，但实践过程中仍然颇有收获。