Максимизируйте количество строк, заканчивающихся определенным символом

Question

Вам дана строка строк, каждое слово разделено пробелами.Вы можете вставить только новые строки в 5-10-й столбец вашей строки.Ваша цель - максимизировать количество строк, заканчивающихся символом x.Как бы вы сделали это, например.

Редактировать: слова могут заканчиваться любым символом. Скажем, вам дан текст

abcdfg cdx abcdx abcdefg aa ggffx ax

, тогда способ их отображения будет

column:
1234567890
abcdfg cdx
abcdx
abcdefg 
aa ggfx
ax

.максимизируйте результат, потому что он имеет 4 строки, которые заканчиваются на x

Я чувствую, что реальная проблема этого вопроса заключается в том, как нам разбить, если он не заканчивается на x, и он находится в позиции, котораяможет сломаться.

Наблюдение

abcdefg 
aa ggfx
ax

Если aa был на 1-й строке с abcdefg, то у нас будет только 1 дополнительная строка из x, потому что ggfx не может сразу прерваться,В результате ggfx ax будет на той же строке

Answer 1

Разрывать строку каждый раз, когда вы можете разорвать строку и встретить соответствующий символ.Если в течение следующих девяти нет целевого персонажа, все время ломайтесь.

К сожалению, это даст оптимальный ответ.Это простая игра.

Было бы более интересно, если бы мы могли забить строки, в которых есть целевой персонаж в некотором диапазоне столбцов (скажем, в столбцах 8-10).Но при подсчете только последнего столбца жадный выигрывает день.

Я предполагаю, что здесь вам разрешено рубить слова без переноса слов или чего-то еще.Но вы не дали нам других правил, так что еще я могу сделать?

String str = "000x0dfkdfjfxxiwrhx fsjhfx fwuhxjhfe xj etc etc you get it";
int doneidx = 0;
char targetchar = 'x';
StringBuffer tmp = new StringBuffer();
while (doneidx < str.length()) {
    if (tmp.length() < 5) {
        tmp.append(str.charAt(doneidx));
    } else {
        for (int i = 0; i < 6; i++) {
            if (doneidx+i < str.length() && str.charAt(doneidx+i) == targetchar) {
                tmp.append(str.substring(doneidx, doneidx+i+1)); 
                doneidx += i+1;
                break;
            }
        }
        System.out.println(tmp.toString());
        tmp = new StringBuffer();
    }
}

Это алгоритм O (N ^ 2).Это может быть уменьшено до O (N), используя памятку.Но, честно говоря, я не думаю, что это имеет здесь значение.

Answer 2

Я бы наивно попробовал что-то вроде следующего псевдокода:

string foo = "abcdfg cdx abcdx ggx"; 
string newFoo = foo; /* Assumes immutable strings */

int startIndex = 5; 
int endIndex = 10; 
int inserts = 0;

for (int i=startIndex-1; i<=endIndex-1 && i<foo.Length-1; i++) 
{ 
 if (foo.Substring(i, 1) == "x") /* Substr is (startIn, length) */ 
 { 
    newFoo = newFoo.Insert(i+1+inserts, "\n");
    inserts++;
 } 
} 

Оставит начальные пробелы, если следующий символ был пробелом на разрывеНе уверен, если это желательно.