Я столкнулся с проблемой, когда делал код 139, разрыв слова.
Учитывая строку s и словарь слова dict, определите, можно ли сегментировать s в разделенную пробелами последовательность из одного или нескольких слов словаря. (каждое словарное слово может быть использовано несколько раз.)
Например, учитывая
s = «leetcode»,
dict = [«leet», «code»].
Верните true, потому что «код leet» может быть сегментирован как «код leet».
Я использую базовый алгоритм динамического программирования, но могу реализовать его иначе, чем популярный в Интернете.
Вот код:
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
int strlen = s.length();
if(0 == strlen) return true;
vector<bool> sepable(false, strlen);
for(int i = 0; i < strlen; ++i) {
if(wordDict.count(s.substr(0,i+1)) > 0) {
sepable[i] = true;
continue;
}
for(int j = 0; j < i; ++j) {
if(sepable[j] && wordDict.count(s.substr(j+1,i-j)) > 0) {
sepable[i] = true;
break;
}
}
}
return sepable[strlen-1];
}
};
Когда я запустил онлайн-тестирование, это не помогло при тестировании: «» aaaaaaa «[» aaaa «,» aa «]», мой код выдает значение true, ожидаемый ответ — false. Однако, если я запускаю его в онлайн-тестировании, он дает правильный результат. Кроме того, он отлично работает на моей собственной виртуальной машине с Clang ++.
Разница между онлайн-судьей и онлайн-тестом заключается в том, что каждый онлайн-тест — это только один тест. Онлайн-судья содержит множество тестов и провалится, если один из тестов не пройдёт. Таким образом, проблема моего кода может заключаться в следующем: при каком-то тесте, отличном от «aaaaaaa», он дает правильный вывод, но вызывает некоторую потенциальную проблему. И именно поэтому мой код потерпит неудачу на «aaaaaaa». Тем не менее, если я просто запустите этот единственный тест, это нормально.
Сайт leetcode говорит, что может, потому что мой код имеет некоторые неопределенные поведения. Предыдущий тестовый пример может повлиять на последний. Я не знаю, каковы все предыдущие тестовые случаи и не ожидал, что кто-нибудь здесь знает об этом. Но я думаю, что пока в моем коде есть проблемы, кто-то может его найти.
Я думаю, что вопрос на этот раз довольно ясен.
параметры этой строки имеют неправильный порядок vector<bool> sepable(false, strlen);
так должно быть vector<bool> sepable(strlen,false);
сначала идет длина вектора, затем значение по умолчанию, и false неявно преобразуется в int, поэтому длина устанавливается равной 0, что дает неопределенное поведение
Других решений пока нет …