Java：在没有内置方法 contains() 的情况下实现 String 方法 contains()
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16122481/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java: Implement String method contains() without built-in method contains()
提问by danksim
I'm trying to implement String method contains()without using the built-in contains()method.
我试图在String method contains()不使用内置contains()方法的情况下实现。
Here is what I have so far:
这是我到目前为止所拥有的：
public static boolean containsCS(String str, CharSequence cs) {
char[] chs = str.toCharArray();
int i=0,j=chs.length-1,k=0,l=cs.length();
//String str = "Hello Java";
// 0123456789
//CharSequence cs = "llo";
while(i<j) {
if(str.charAt(i)!=cs.charAt(k)) {
i++;
}
if(str.charAt(i)==cs.charAt(k)) {
}
}
return false;
}
I was just practicing my algorithm skills and got stuck.
我只是在练习我的算法技能并被卡住了。
Any advice?
有什么建议吗？
回答by Kamal Garg
Using Only 1 Loop
仅使用 1 个循环
I did some addition to Poran answer and It works totally fine:
我对 Poran 的回答做了一些补充，它完全正常：
public static boolean contains(String main, String Substring) {
boolean flag=false;
if(main==null && main.trim().equals("")) {
return flag;
}
if(Substring==null) {
return flag;
}
char fullstring[]=main.toCharArray();
char sub[]=Substring.toCharArray();
int counter=0;
if(sub.length==0) {
flag=true;
return flag;
}
for(int i=0;i<fullstring.length;i++) {
if(fullstring[i]==sub[counter]) {
counter++;
} else {
counter=0;
}
if(counter==sub.length) {
flag=true;
return flag;
}
}
return flag;
}
回答by Arif Nadeem
This should work fine..I am printing execution to help understand the process.
这应该可以正常工作..我正在打印执行以帮助理解该过程。
public static boolean isSubstring(String original, String str){
int counter = 0, oLength = original.length(), sLength = str.length();
char[] orgArray = original.toCharArray(), sArray = str.toCharArray();
for(int i = 0 ; i < oLength; i++){
System.out.println("counter at start of loop " + counter);
System.out.println(String.format("comparing %s with %s", orgArray[i], sArray[counter]));
if(orgArray[i] == sArray[counter]){
counter++;
System.out.println("incrementing counter " + counter);
}else{
//Special case where the character preceding the i'th character is duplicate
if(counter > 0){
i -= counter;
}
counter = 0;
System.out.println("resetting counter " + counter);
}
if(counter == sLength){
return true;
}
}
return false;
}
回答by 0x6C38
As JB Nizet suggested, hereis the actual code for contains():
正如 JB Nizet 所建议的，这里是实际的代码contains()：
2123 public boolean contains(CharSequence s) {
2124 return indexOf(s.toString()) > -1;
2125 }
And here is the code for indexOf():
这是代码indexOf()：
1732 public int indexOf(String str) {
1733 return indexOf(str, 0);
1734 }
Which leads to:
这导致：
1752 public int indexOf(String str, int fromIndex) {
1753 return indexOf(value, offset, count,
1754 str.value, str.offset, str.count, fromIndex);
1755 }
Which finally leads to:
这最终导致：
1770 static int indexOf(char[] source, int sourceOffset, int sourceCount,
1771 char[] target, int targetOffset, int targetCount,
1772 int fromIndex) {
1773 if (fromIndex >= sourceCount) {
1774 return (targetCount == 0 ? sourceCount : -1);
1775 }
1776 if (fromIndex < 0) {
1777 fromIndex = 0;
1778 }
1779 if (targetCount == 0) {
1780 return fromIndex;
1781 }
1782
1783 char first = target[targetOffset];
1784 int max = sourceOffset + (sourceCount - targetCount);
1785
1786 for (int i = sourceOffset + fromIndex; i <= max; i++) {
1787 /* Look for first character. */
1788 if (source[i] != first) {
1789 while (++i <= max && source[i] != first);
1790 }
1791
1792 /* Found first character, now look at the rest of v2 */
1793 if (i <= max) {
1794 int j = i + 1;
1795 int end = j + targetCount - 1;
1796 for (int k = targetOffset + 1; j < end && source[j] ==
1797 target[k]; j++, k++);
1798
1799 if (j == end) {
1800 /* Found whole string. */
1801 return i - sourceOffset;
1802 }
1803 }
1804 }
1805 return -1;
1806 }
回答by Stephen C
Hints:
提示：
- Use a nested loop.
- Extracting the chars to an array is probably a bad idea. But if you are going to do it, you ought to use it!
- Ignore the suggestion to use fast string search algorithms. They are only fast for large scale searches. (If you look at the code for
String.indexOf, it just does a simple search ...)
- 使用嵌套循环。
- 将字符提取到数组可能是一个坏主意。但如果你要这样做，你应该使用它！
- 忽略使用快速字符串搜索算法的建议。它们仅适用于大规模搜索。（如果您查看 的代码
String.indexOf，它只会进行简单的搜索...）
回答by Mo Beigi
I came up with this:
我想出了这个：
public static boolean isSubString(String s1, String s2) {
if (s1.length() > s2.length())
return false;
int count = 0;
//Loop until count matches needle length (indicating match) or until we exhaust haystack
for (int j = 0; j < s2.length() && count < s1.length(); ++j) {
if (s1.charAt(count) == s2.charAt(j)) {
++count;
}
else {
//Redo iteration to handle adjacent duplicate char case
if (count > 0)
--j;
//Reset counter
count = 0;
}
}
return (count == s1.length());
}
回答by Peter V
I have recently stumbled upon this problem, and though I would share an alternative solution. I generate all the sub strings with length of the string we looking for, then push them into a hash set and check if that contains it.
我最近偶然发现了这个问题，尽管我会分享一个替代解决方案。我生成所有具有我们要查找的字符串长度的子字符串，然后将它们推入一个哈希集并检查其中是否包含它。
static boolean contains(String a, String b) {
if(a.equalsIgnoreCase(b)) {
return true;
}
Set<String> allSubStrings = new HashSet<>();
int length = b.length();
for(int i=0; i<a.length(); ++i) {
if(i+length <= a.length()) {
String sub = a.substring(i, i + length);
allSubStrings.add(sub);
}
}
return allSubStrings.contains(b);
}
回答by Shishir
public static boolean contains(String large, String small) {
char[] largeArr = large.toCharArray();
char[] smallArr = small.toCharArray();
if (smallArr.length > largeArr.length)
return false;
for(int i = 0 ; i <= largeArr.length - smallArr.length ; i++) {
boolean result = true ;
for(int j = 0 ; j < smallArr.length ; j++) {
if(largeArr[i+j] != smallArr[j]) {
result = false;
break;
}
result = result && (largeArr[i+j]==smallArr[j]);
}
if(result==true) {return true;}
}
return false;
}
回答by Anil M
Certainly not the most efficient solution due to the nested loop, but it seems to work pretty well.
由于嵌套循环，当然不是最有效的解决方案，但它似乎工作得很好。
private static boolean contains(String s1, String s2) {
if (s1.equals(s2)) return true;
if (s2.length() > s1.length()) return false;
boolean found = false;
for (int i = 0; i < s1.length() - s2.length(); i++) {
found = true;
for (int k = 0; k < s2.length(); k++)
if (i + k < s1.length() && s1.charAt(i + k) != s2.charAt(k)) {
found = false;
break;
}
if (found) return true;
}
return false;
}
回答by Poran
It can be done using a single loop.
它可以使用单个循环来完成。
public boolean StringContains(String full, String part) {
long st = System.currentTimeMillis();
if(full == null || full.trim().equals("")){
return false;
}
if(part == null ){
return false;
}
char[] fullChars = full.toCharArray();
char[] partChars = part.toCharArray();
int fs = fullChars.length;
int ps = partChars.length;
int psi = 0;
if(ps == 0) return true;
for(int i=0; i< fs-1; i++){
if(fullChars[i] == partChars[psi]){
psi++; //Once you encounter the first match, start increasing the counter
}
if(psi == ps) return true;
}
long et = System.currentTimeMillis()- st;
System.out.println("StringContains time taken =" + et);
return false;
}
