于issubstring递归方法

下面是调用递归方法的代码：于issubstring递归方法

if (isSubstring(str1, str2)) 
    System.out.println ("\"" + str1 + "\" is a substring of " + 
         "\"" + str2 + "\""); 
else 
    System.out.println ("\"" + str1 + "\" is not a substring of " + 
         "\"" + str2 + "\"");

这是我到目前为止已经完成了方法，它几乎工作：

public static boolean isSubstring(String str, String target) 
{ 
    if (target.length() == 0) 
     return false; 

    if (str.equals(target)) 
     return true; 

    else  
     return (isSubstring(str, target.substring(0,target.length()-1)));    
}

所以它的工作原理如果str1作为“zzz”传递，str2作为“zzzabcdef”传递，那么它将返回true。但是，如果str2是“abczzzxx”或“abczzz”，它不会返回true。有没有人有任何建议或想法？

来源

2012-11-08 Matt Andrzejczuk

你的方法可能是一条线件事：'回报str.contains（目标）;' – assylias

我注意到你的'如果（target.length（）== 0）'声明。你可能想要对str和target进行一些空的检查。我喜欢使用'StringUtils.isBlank（）'方法;看到http://commons.apache.org/lang/api-2.5/org/apache/commons/lang/StringUtils.html#isBlank(java.lang.String） –

@assylias我想重点是做递归作为练习 – maasg

是的 - 基本上你的递归方法总是取掉最后一个字符，然后递归，直到得到一个空字符串或者值为等于为第一个字符串。

这意味着只有可能地方它可以找到第一个字符串是在目标字符串的开始，这意味着它真的是一个startsWith方法。这将是惊人，低效

一种选择，但我认为应该努力将尝试采取一个字符关闭前和尝试采取的字符关底（独立）：

return isSubstring(str, target.substring(0, target.length() - 1)) 
    || isSubstring(str, target.substring(1));

来源

2012-11-08 15:59:29

哎唷，那是O（2^n）？ – maasg

@maasg：我怀疑是这样......这当然很可怕。 –

尝试

public static boolean isSubstring(String str, String target) { 
      System.out.println("target :" + target); 
      if (str.equals(target)) 
       return true; 
      else if (str.length() > target.length()) 
       return false; 
      else 
       return (isSubstring(str, target.substring(1, target.length()))) 
         || (isSubstring(str, 
           target.substring(0, target.length() - 1))); 
     }

这应该递归地尝试从目标的所有子字符串。

来源

2012-11-08 16:10:44

目前，您只能从字符串末尾删除字符。你的函数可以被正确调用startsWith(...)

对于字符串匹配，我想尝试以下算法中：

删除字符从主字符串，而没有匹配。开始在匹配字符串时使用这两个字符串，直到匹配子字符串的所有连续字符，或者直到找到不匹配的字符，这将允许您提前停止。

事情是这样的：

boolean isSubString(String s1, String s, boolean match) { 
    if (s1 == "") return true; 
    if (s == "") return false; 
    if ((s1.charAt(0) != s.charAt(0)) && match) return false; //failfast 
    if (s1.charAt(0) == s.charAt(0)) return isSubString(s1.substring(1), s.substring(1), true); 
    return isSubString(s1.substring(1), s.substring(1), match); 
} 

boolean isSubString(String s1, String s) { 
    return isSubString(s1, s,false); 
}

来源

2012-11-08 16:17:41 maasg

于issubstring递归方法

回答

相关问题