非死不可店面， 挂

EE职位。

题目：
input： String[] words, char[] orders
output: if the words are in the order define

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

e/smiley/QQ/em03.gif" smilieid="85" border="0" alt="" />。应该挂了吧。

写了一下，但是前提条件是所有vector里面的字符都包含在字典order里面。。不知道对不对
/*
input： String[] words, char[] orders
output: if the words are in the order defined by orders.

for example:. 1point 3acres 论坛
["cc", "cb", "ab"], {c, b, a}  => true

["cc", "cb", "ab"], {b, c, a}  => false
*/
bool check(string s1, string s2, unordered_map<char,int> m)
{
    if(s1 == s2)return true;
    int len = s1.size() > s2.size() ? s2.size() : s1.size();
    for(int i = 0; i < len; i++)
    {
        if(m[s1[i]] > m[s2[i]])return false;
        if(m[s1[i]] < m[s2[i]])return true;
    }
    return s2.size() > len ? true : false;
}
bool valid(vector<string> v, vector<char> dict)
{
    unordered_map<char,int> m;
    for(int i = 0; i < dict.size(); i++)
    {
        m[dict[i]] = i;
    }
    for(int i = 1; i < v.size(); i++)
    {
        if(!check(v[i - 1], v[i], m))return false;
    }
    return true;
}

int main() {
        // your code goes here
        vector<string> v1 = {"cc", "cb", "ab"};
        vector<string> v2 = {"cc", "cb", "ab"};
        vector<char> dict1 = {'c', 'b', 'a'};
        vector<char> dict2 = {'b', 'c', 'a'};
        cout<<valid(v1, dict1)<<endl;
        cout<<valid(v2,dict2)<<endl;
        return 0;
}

Vicmal 发表于 2018-11-8 10:59
请问下楼主给的什么解法？感觉这道题只能比较相邻的 然后for 每个位置的字符 看每个字符在给的order里面对 ...

我差不多是这么写的，
foreach words[i-1] , words[i] pair, find the first characters of words[i-1] and words[i] from left and compare if words[i-1][j] < words[i][j].
烙印不理解，他觉得需要先对每个词的第一个char比较，然后第二个char。类似radix sort，我觉得没那么复杂。

补充内容 (2018-11-9 10:48):
有些自动格式问题，补充一下以免误解。
foreach words[i-1] , words【i】  pair, find the first characters of words[i-1] and words【i】 from left and compare if words[i-1][j] < words【i】[j].

jih23 发表于 2018-11-9 09:24
我差不多是这么写的，
foreach words , words pair, find the first characters of words and words fr ...

遇到这种烙印也没办法，楼主应该给他解释了比较可以传递的。。这道题只需要返回true或者false就可以了，如果需要重新排序才需要radix sort，这烙印有毒. 楼主加油！

请问下楼主给的什么解法？感觉这道题只能比较相邻的 然后for 每个位置的字符 看每个字符在给的order里面对应的rank 返回true or false就好了 烙印是要什么样的解法呢 谢谢楼主 加米了

用trie 吧 每节点记录和以前visit过的最大的比 不能更小

电话通知你了吗？可能加面

祝楼主好运，不是太理解第一个例子，为什么“ab" 还是return true，能解释一下嘛？

twopointers的题吧…？

有点像alien words, 只不过变成判断valid而不是找一个顺序了

mingzhou1987 发表于 2018/11/08 11:11:17
祝楼主好运，不是太理解第一个例子，为什么“ab" 还是return true，能解释一下嘛？

这个例子能够得出c在b前面，c在a前面，a和b的顺序随意所以是true

leetcode 791, custom stor string.