byd6540
(比亚迪)
1
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,他要回去看看 。应该挂了吧。
wx1408
(星岛)
2
请问下楼主给的什么解法?感觉这道题只能比较相邻的 然后for 每个位置的字符 看每个字符在给的order里面对应的rank 返回true or false就好了 烙印是要什么样的解法呢 谢谢楼主 加米了
DMGY
(大漠孤烟)
3
用trie 吧 每节点记录和以前visit过的最大的比 不能更小
stn5755
(桑塔纳)
5
祝楼主好运,不是太理解第一个例子,为什么“ab" 还是return true,能解释一下嘛?
有点像alien words, 只不过变成判断valid而不是找一个顺序了
0572C
(豆豆)
8
这个例子能够得出c在b前面,c在a前面,a和b的顺序随意所以是true
stn5755
(桑塔纳)
9
写了一下,但是前提条件是所有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;
}
0572C
(豆豆)
10
leetcode 791, custom stor string.