Pinterest 2018.10.25 OA详细描述 求加米

Pinterest给了四小时，结果只有一个题。我做了两小时就交了，事后在想是不是还有更优解法。我当时是写了一个bfs。

给定一个由字母组成的矩阵，从任意一格出发，找出由相邻字母组成的最长路径。
相邻字母的定义是当前格子字母的前后字母，例如B的相邻字母就是A和C。
在矩阵中移动时，可以向上下左右四个方向移动。
例如：<

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

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

ong>
对不起我把例子写错了
ABEF
ECDD
ADXC
BCXE
应该是这样
然后最长路径是ABCDCB

补充内容 (2018-10-28 12:00):
请问有没有办法编辑原帖，我想给内容加一个101分的阅读限制。

A

B

E

F

收藏2 淘帖0

好苗1 杂草0

评分

参与人数 13	大米 +52	收起 理由
蓝豚子	+ 5	给你点个赞！
spaCycraft	+ 5	很有用的信息！
zhangy405	+ 3	很有用的信息！
MatchaCake	+ 5	给你点个赞！
AngelSeven	+ 3	很有用的信息！

查看全部评分

上一篇：关于dropbox电面后的下一步
下一篇：推理哦 OA 近期题型总结

相关帖子

• google 面试
• HRT SWE Intern 2025
• Amazon L4 店面挂经
• 微末昂赛挂经
• Stripe⚡️面
• 2026 new grad Color Health OA + screening + 店面 掛經
• 数据🧱店面
• 麻alexa shopping挂经
• 求问 Apple 这种情况正常吗？
• 避雷超人公司
• WorkDay Sr SDE - Evisort 求电面面经
• Stripe OA UTC跨周时区映射 + 双指针滑动窗口
• 交易桌OA
• 求加米 Meta NG 详细面经
• Snowflake 2026 Fall Intern
• 请问 google r1后多久能收到结果
• Burning Rope
• Meta Recruiter Screen
• IBM Confluent Knockri Recorded Competency Interview
• IBM Confluent HackerRank 在线笔试

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

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

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

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

Arjen 发表于 2018-10-28 13:24
想问一下大佬，我也想到了DFS，但只能到在每个点都进行一次DFS的方法。这样显然有很多重复搜索，大佬有什 ...

没想到什么量级上可以提高时间复杂度的算法，虽然有办法可以剪枝以减少运算量。

这道题如果真的允许ABCBA这样的话，用BFS 不行。BFS 如何保证你不会陷入无限循环 ？你只能记录曾经到过的点并保证以后不再到这些点，可是，这种情况下你可能找不到最长的那条路径，因为最长的那条路径可能用到已经到过的点。比如，一条最长线可能是ABCCBABCD，而可能这个D已经早先被另外一ABCD用过了。用DFS不会有这个问题。

谢谢楼主！

请问一下楼主！什么叫“由相邻字母组成的最长路径”？ABCCBA中，C和C为啥是相邻字母啊？而且这题ABCDEF在这题里也是符合要求的吧～

Arjen 发表于 2018-10-28 11:37
请问一下楼主！什么叫“由相邻字母组成的最长路径”？ABCCBA中，C和C为啥是相邻字母啊？而且这题ABCDEF在这 ...

我把例子写错了，不好意思，你看补充。

论坛匿名用户 发表于 2018-10-28 11:49
我把例子写错了，不好意思，你看补充。

已加米！谢谢

tudoucc86 发表于 2018-10-28 12:00
试试这个：
ABC
BCD

想问一下大佬，我也想到了DFS，但只能到在每个点都进行一次DFS的方法。这样显然有很多重复搜索，大佬有什么更好的方法吗～