给定一个子环和一个字符串的列表,如果它是一个子字符串,请打印出列表中的项目。
在不使用任何子字符串方法的情况下执行此操作的最有效方法是什么?
例:
输入:["cat", "dog", "foo", "foopoo", "foopo", "nope", "dogf"]
输出:"catdogfoopoo"
解释:
"c"位于地图中的索引 0 处。
遍历"cat"的长度,并比较它是否与从0到"cat"的长度相同
如果是,请打印。
我的想法:
所以到目前为止我的想法是,您将遍历给定的字符串并将每个字符映射到索引的数组列表
<(c, [0]), (a, [1]), (r, [2]), (d, [3]), (o, [4,7,8,10,11]), (g, [5]), (f, [6]), (p, [4])>
然后循环遍历子字符串列表。
for (int x = 0; x < list.length; x++) {
String s = list.get(x);
if (s.get(s.charAt(0)) != null)
//loop through, comparing from whether the word is in the string
但这并没有利用这样一个事实,即如果已经发现"foo"是一个子字符串,那么检查"foopoo"是否是一个子字符串应该很容易(没有遍历foo)。
我有点卡在那里,因为我相信有一种更有效的方法可以做到这一点。不使用"包含"或其他什么(这不是更有效)
for(int i=0; i < array.length; i++){
if(input.contains(array[i])){
System.out.println(array[i]);
}
}
这应该是涵盖此问题的解决方案。
String text = "cardogfoopoo";
for (int x = 0; x < list.length; x++) {
if(text.containts(list[x])
System.out.println(list[x] + " is a substring!");
}
也许你应该对子字符串进行排序并生成一个类似于下面的数据结构(它是一个链表数组):
[0] cat
[1] dog -> f
[2] foo -> po -> o
[3] nope
在这个结构中,你可以找到子字符串"dog"和"dogf",以及"foo","foopo"和"foopoo"。它类似于在字典中搜索。
你从"catdogfoopoo"字符串的索引0开始,开始搜索字典,即查找以"c"开头的条目。您发现结构的索引 0 包含"c",因此您决定遍历其长度。所以你取条目长度(3个字符),看看从索引0开始的三个字符是否等于它(这是一个字符串比较,它无济于事)。它们是,所以你打印"cat",因为你找到了包含在字符串中的整个条目。
下一个索引是 3,即字符"d",并且您位于字典位置 [0] 的第一个条目。此位置没有其他条目,因此您必须查找以"d"开头的其他条目,以便找到"dog"作为位置 [1] 的第一个条目。您将此条目(由三个字符组成)与字符串中从索引 4 开始的字符进行比较,您会发现它们是相等的,因此您打印了"dog"。下一个索引是 6,你将其与下一个条目"f"进行比较,你会发现它们是相等的,所以你打印了"dogf"。
依此类推,直到您打印"foo","foopo"和"foopoo"。
希望清楚。如果您觉得有用,我可以提供有关我如何创建结构的详细信息。