店面一挂

问了一道莫名其妙的题。。不会做。。。地理大神会做的话可以说一下：

在vector中给你一个类似这样的["cabc"

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

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

存在这样的string

但是面试官希望的是不用额外空间。。这个怎么办

遍历vector，按顺序依次找“csg”的各个字符？

yishuihe 发表于 2018-5-9 15:39
遍历vector，按顺序依次找“csg”的各个字符？

不行吧，比如说["cabc", "ts", "erg"]我要找的是tcb,要是先在第一个中找的话不就miss了t了么

不确定我是不是把题目理解正确了，
比如说["cabc", "ts", "erg"]我要找的是tcb
那么我们依次在list中找t c b。同时记录已经找过的list中的string，不能重复从list的start找，因为题目要求“要保持顺序不变”

1. boolean findStr(List<String> list, String target) {
   
2.     int listIndex = 0;
   
3.     for(char c : target) {
   
4.         boolean foundC = false;
   
5.         for(int i = listIndex; i < list.size(); i++) {
   
6.             if(list.get(i).indexOf(c) != -1) {
   
7.                 foundC = true;
   
8.                 listIndex = i + 1;//这里不严谨，我假设只能从list中的单词里面找一个char
   
9.                 break;
   
10.             }
    
11.         }
    
12.         if(!foundC) return false;
    
13.     }
    
14. 
    
15.     return true;
    
16. }

复制代码

感觉像dfs的题，不知道是不是只能朝右上或者右下走的那种。类似理扣七十九

yishuihe 发表于 2018-5-10 04:03
不确定我是不是把题目理解正确了，
比如说["cabc", "ts", "erg"]我要找的是tcb
那么我们依次在list中找t  ...

你这个相当于复杂度是O（targetLen * listvectorSize）吧

catherinez 发表于 2018-5-10 04:29
感觉像dfs的题，不知道是不是只能朝右上或者右下走的那种。类似理扣七十九

这个跟期9应该没关系吧。因为这个距离定，要是dfs的话相当于还要对每一个距离再来一个loop

楼主可以稍微详细说一下题目吗？保持顺序不变是什么意思。。

Joseph199209 发表于 2018-5-10 05:06
楼主可以稍微详细说一下题目吗？保持顺序不变是什么意思。。

就是先找到c,再找到s,再找到g。然后就是如果在同一word中找到的话。比如说word是cag，要先找到c再找到g

楼主能再多举几个例子嘛？想看看例子是咋得到这个结果的，实在没看懂