非死不可店面, 挂

EE职位。

题目:
input: String[] words, char[] orders
output: if the words are in the order defined by orders.

for example:
[“cc”, “cb”, “ab”], {c, b, a} => true

[“cc”, “cb”, “ab”], {b, c, a} => false

快速写了一个, 结果烙印怀疑不能work,我不能说服他,他不能指出bug。想跑几个test,他说手动演示几个test case 给他看,最后半小时都用在这里。最后说可能work,可能不work,他要回去看看 。应该挂了吧。

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

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

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

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

twopointers的题吧…?

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

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

写了一下,但是前提条件是所有vector里面的字符都包含在字典order里面。。不知道对不对

/*
input: String[] words, char[] orders
output: if the words are in the order defined by orders.

for example:
["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;
}

leetcode 791, custom stor string.