將字符串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; 
    } 
    } 
}