将字符串N拆分为4个不同的字符串

Question

字符串必须拆分为4个配对不同的非空白部分。例如，

• "happynewyear"可以成为["happy", "new", "ye" and "ar"]

没有缺失，字符的顺序变化是允许的。

这个问题是网络竞赛的一部分，现在已经结束。我已经写了下面的C＃代码，它适用于我已经运行的测试用例，但在提交之后，它在3个测试用例中失败。我不知道我可能会错过哪些情况，有谁能帮忙？

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace Hackerearth___India_Hacks 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      var line1 = System.Console.ReadLine().Trim(); 
      var N = Int32.Parse(line1); 
      string[] s = new string[N]; 
      string result = ""; 
      for (var i = 0; i < N; i++) 
      { 
       s[i] = System.Console.ReadLine().Trim(); 
       result = result + "\n" + check(s[i]); 
      } 
      System.Console.Write(result); 
      Console.ReadKey(); 
     } 
     static string check(string s) 
     { 
      if (s.Length > 3) 
      { 
       string[] s1 = new string[4]; 
       int k = 0; 
       string c = ""; 
       foreach (char ch in s) 
       { 
        c = c + ch.ToString(); 

        // Console.WriteLine("C :" +c); 
        if (k == 0) 
        { 
         s1[k] = c; 
         c = ""; 
         k = 1; 
        } 
        else 
         for (int i = 0; i < k; i++) 
         { 
          int f = 0; 
          for (int j = 0; j < k; j++) 
          { 
           if (s1[j].Equals(c) || c == "") 
            f=1; 
          } 
          if (f == 1) 
           break; 
          s1[k] = c; 
          c = ""; 

          if (k == 3 && s1[k] != null) 
           return "YES"; 
          k++; 
         //   Console.WriteLine("K :"+s[k]); 
        } 

       } 
       return "NO"; 

      } 
      else 
      { 
       return "NO"; 
      } 
     } 
    } 
} 

Answer 1

这将是一个不适用于您的算法的示例："aababa"。根据您的标准，4个字符串应该是["aa", "b", "a","ba"]，但是您的算法始终假定第一个字符是解决方案中的第一个字符串。这个假设是错误的。如果"a"是我给出示例中的第一个字符串，那么您的算法将失败，因为它会使前3个字符串["a", "ab", "aba",...]最后一个与您的算法一起失败，因为它没有更多字符添加到数组中。

递归解决方案对我来说很有意义......下面是我认为可行的一些代码。

编辑：它的工作... here's a dotnetfiddle

public static List<string> FindStrings(string s, int n) { 
    if (n == 0) { 
     if (string.IsNullOrEmpty(s)) { 
      return new List<string>{ }; 
     } 
     return null; // null means invalid 
    } 

    for (var i=s.Length-1; i>=0; i--){ 
     var startOfString = s.Substring(0, i); 
     var endOfString = s.Substring(i); 
     var list = FindStrings(startOfString, n-1); 

     // invalid... gotta continue to next try 
     if (list == null) continue; 

     // make sure there are no matches so far 
     if (list.Contains(endOfString)) continue; 

     // bingo! 
     if (list.Count == n-1) { 
      list.Add(endOfString); 
      return list; 
     } 
    } 

    return null; // null means invalid 
} 

Answer 2

一个解决这个问题的办法是解决创建所有可能的子串的问题。然后通过所有可能性并确保结果是不同的。

private static void Main(string[] args) 
{ 
    var N = int.Parse(Console.ReadLine()); 
    for (var i = 0; i < N; i++) 
    { 
    Console.WriteLine(IsPairwiseUnquie(Console.ReadLine(), 4) ? "YES" : "NO"); 
    } 
} 

public static bool IsPairwiseUnquie(string s, int count) 
{ 
    return s.AllSubstrings(4).Any(subs => subs.Count == subs.Distinct().Count()); 
} 

public static IEnumerable<List<string>> AllSubstrings(this string str, int count) 
{ 
    if(str.Length < count) 
    throw new ArgumentException("Not enough characters"); 
    if(count <= 0) 
    throw new ArgumentException("Must be greater than 0", nameof(count)); 

    // Base case of only one substring, just return the original string. 
    if (count == 1) 
    { 
    yield return new List<string> { str }; 
    yield break; 
    } 

    // break the string down by making a substring of all possible lengths from the first n 
    // then recursively call to get the possible substrings for the rest of the string. 
    for (int i = 1; i <= str.Length - count + 1; i++) 
    { 
    foreach (var subsubstrings in str.Substring(i).AllSubstrings(count - 1)) 
    { 
     subsubstrings.Insert(0, str.Substring(0, i)); 
     yield return subsubstrings; 
    } 
    } 
}