c# - 字符串算法C#的组合

Question

所以我最近接受了一次采访，其中一个问题如下。我一直在思考如何解决这个问题。有人知道吗？我发现这与字符串算法的组合有关。

由和string组成。任务是将其拆分为单独的部分，以便每个部分包含相同数量的字母。可以用多少种方式拆分字符串。'x''y'3'y'

例如：

输入："xyxyy"

输出："xy | xy | y", "xyx | y | y"

如果有人能给我一些关于我需要知道什么来解决这个问题的线索，或者更好的是，如果你展示一个解释如何做到这一点的代码，那就太好了！

谢谢

标签： c#stringalgorithmsubstring

Answer 1

Simple math will do. So you have a string with 3n 'y' (otherwise you can't split the string at all). The string is something like this:

 aybcdy ... eypq...raybcdy ...  eyvw..zybcdy ...  ey
 <--- n 'y'-->       <--- n 'y'-->     <--- n 'y'-->    

Note that chunks with y a fixed but characters between these parts can be added either to one part or to another:

aybcdy ... ey | pq...raybcdy ...  ey # 1st possibility
<--- n 'y'-->          <--- n 'y'-->

aybcdy ... eyp | q...raybcdy ...  ey # 2nd possibility
<--- n 'y'-->          <--- n 'y'-->

aybcdy ... eypq | ...raybcdy ...  ey # 3d possibility
<--- n 'y'-->          <--- n 'y'-->

...

aybcdy ... eypq...ra | ybcdy ...  ey # the last possibility
<--- n 'y'-->          <--- n 'y'-->

So far we have (P + 1) * (Q + 1) possibilities to split the string into 3 chunks where

• P - characters between N-th and N+1-st 'y'
• Q - characters between 2N-th and 2N+1-st 'y'

Code:

private static int Solution(string value) {
  if (null == value)
    return 0;

  int N = value.Count(c => c =='y');

  if (N % 3 != 0 || N == 0) // let's return 0 if we don' have 'y's
    return 0;

  N = N / 3;

  int P = 0;
  int Q = 0;   
  int y = 0;

  foreach (char c in value) {
    if (c == 'y')
      y += 1;
    else if (y == N)
      ++P;
    else if (y == 2 * N) 
      ++Q;
  }

  return (P + 1) * (Q + 1);
}

Demo:

Console.Write(Solution("xyxyy")); 

Outcome:

2

If you want to obtain splits:

private static IEnumerable<string[]> SolutionSplits(string value) {
  if (null == value)
    yield break;

  int N = value.Count(c => c == 'y');

  if (N % 3 != 0 || N == 0) // let's return empty if we don' have 'y's
    yield break;

  N = N / 3;

  List<int> P = new List<int>();
  List<int> Q = new List<int>();
  int y = 0;

  for (int i = 0; i < value.Length; ++i) {
    char c = value[i];

    if (c == 'y')
      y += 1;

    if (y == N)
      P.Add(i);
    else if (y == 2 * N)
      Q.Add(i);
  }

  foreach (int p in P)
    foreach (int q in Q)
      yield return new string[] {
        value.Substring(0, p + 1),
        value.Substring(p + 1, q - p),
        value.Substring(q + 1)}; 
}

Demo:

 string source = "xyxyy";
 
 Console.Write(string.Join(Environment.NewLine, SolutionSplits(source)
   .Select(items => string.Join(" | ", items)));

Outcome:

 xy | xy | y
 xyx | y | y