面试问题 - 根据规则将文本拆分为子字符串

Question

根据以下规则将文本拆分为子字符串:

• a)每个子串的长度应小于或等于M.
• b)如果子字符串包含任何数字字符,则子字符串的长度应小于或等于N(N <M)
• c)子串的总数应尽可能小

我不知道如何解决这个问题,我猜它与"动态编程"有关.任何人都可以帮我用C#或Java实现它吗？非常感谢.

Answer 1

理念

一种贪婪的方法是要走的路:

• 如果当前文本为空,则表示您已完成.
• 取前N个字符.如果它们中的任何一个是数字,那么这是一个新的子字符串.把它砍掉然后开始吧.
• 否则,将无数字段扩展到最多M个字符.这是一个新的子字符串.把它砍掉然后开始吧.

证明

这是一个reductio-ad-absurdum证明,以上产生了最佳解决方案.假设有比贪婪分裂更好的分裂.让我们跳到两个分裂开始不同的点,并在此之前删除所有内容.

情况1)前N个字符中的一个数字.

假设有一个输入,其中切掉前N个字符不能产生最佳解决方案.

Greedy split:   |--N--|...
A better split: |---|--...
                      ^
                      +---- this segment can be shortened from the left side

但是,推定的更好的解决方案的第二部分可以始终从左侧缩短,第一部分扩展到N个字符,而不改变段的数量.因此,矛盾:这种分裂并不比贪婪的分裂更好.

情况2)第一个K(N <K <= M)字符中没有数字.

假设存在一个输入,其中切掉前K个字符不能产生最佳解.

Greedy split:   |--K--|...
A better split: |---|--...
                      ^
                      +---- this segment can be shortened from the left side

同样,"更好"的分裂可以在不改变分段数量的情况下转换为贪婪分裂,这与最初的假设相矛盾,即最初的假设比贪婪的分裂更好.

因此,贪婪的分裂是最佳的.QED

实现(Python)

import sys

m, n, text = int(sys.argv[1]), int(sys.argv[2]), sys.argv[3]
textLen, isDigit = len(text), [c in '0123456789' for c in text]

chunks, i, j = [], 0, 0
while j < textLen:
   i, j = j, min(textLen, j + n) 
   if not any(isDigit[i:j]):
      while j < textLen and j - i < m and not isDigit[j]:
         j += 1
   chunks += [text[i:j]]
print chunks

实现(Java)

public class SO {
   public List<String> go(int m, int n, String text) {
      if (text == null)
         return Collections.emptyList();
      List<String> chunks = new ArrayList<String>();

      int i = 0;
      int j = 0;
      while (j < text.length()) {
         i = j;         
         j = Math.min(text.length(), j + n);
         boolean ok = true;
         for (int k = i; k < j; k++) 
            if (Character.isDigit(text.charAt(k))) {
               ok = false;              
               break;                   
            }                   
         if (ok)        
            while (j < text.length() && j - i < m && !Character.isDigit(text.charAt(j)))
               j++;                     
         chunks.add(text.substring(i, j));
      }         
      return chunks;
   }    

   @Test
   public void testIt() {
      Assert.assertEquals(
         Arrays.asList("asdas", "d332", "4asd", "fsdxf", "23"),
         go(5, 4, "asdasd3324asdfsdxf23"));
   }    
}