Given a sentence that consists of some words separated by a single space, and a searchWord.

You have to check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string S is any leading contiguous substring of S.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Example 4:

Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4

Example 5:

Input: sentence = "hello from the other side", searchWord = "they"
Output: -1

Constraints:

1 <= sentence.length <= 100
1 <= searchWord.length <= 10
sentence consists of lowercase English letters and spaces.
searchWord consists of lowercase English letters.

Solution 1: Brute Force

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

int isPrefixOfWord(string sentence, string searchWord) {

const int n = sentence.size();

const int l = searchWord.size();

int word = 0;

for (int i = 0; i <= n - l; ++i) {

if (i == 0 || sentence[i - 1] == ' ') {

++word;

bool valid = true;

for (int j = 0; j < l && valid; ++j)

valid = valid && (sentence[i + j] == searchWord[j]);

if (valid) return word;

}

return -1;

}

};

https://leetcode.com/problems/word-ladder/description/

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Idea:

BFS

Time Complexity: O(n*26^l) -> O(n*26^l/2), l = len(word), n=|wordList|

Space Complexity: O(n)

Solution 1: BFS

C++

// Author: Huahua

// Running time: 93 ms

class Solution {

public:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return 0;

queue<string> q;

q.push(beginWord);

int l = beginWord.length();

int step = 0;

while (!q.empty()) {

++step;

for (int size = q.size(); size > 0; size--) {

string w = q.front();

q.pop();

for (int i = 0; i < l; i++) {

char ch = w[i];

for (int j = 'a'; j <= 'z'; j++) {

w[i] = j;

// Found the solution

if (w == endWord) return step + 1;

// Not in dict, skip it

if (!dict.count(w)) continue;

// Remove new word from dict

dict.erase(w);

// Add new word into queue

q.push(w);

}

w[i] = ch;

}

return 0;

}

};

Java

// Author: Huahua

// Running time: 92 ms (<76.61%)

class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>();

for (String word : wordList) dict.add(word);

if (!dict.contains(endWord)) return 0;

Queue<String> q = new ArrayDeque<>();

q.offer(beginWord);

int l = beginWord.length();

int steps = 0;

while (!q.isEmpty()) {

++steps;

for (int s = q.size(); s > 0; --s) {

String w = q.poll();

char[] chs = w.toCharArray();

for (int i = 0; i < l; ++i) {

char ch = chs[i];

for (char c = 'a'; c <= 'z'; ++c) {

if (c == ch) continue;

chs[i] = c;

String t = new String(chs);

if (t.equals(endWord)) return steps + 1;

if (!dict.contains(t)) continue;

dict.remove(t);

q.offer(t);

}

chs[i] = ch;

}

return 0;

}

Solution 2: Bidirectional BFS

C++

// Author: Huahua

// Running time: 32 ms (better than 96.6%)

class Solution {

public:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return 0;

int l = beginWord.length();

unordered_set<string> q1{beginWord};

unordered_set<string> q2{endWord};

int step = 0;

while (!q1.empty() && !q2.empty()) {

++step;

// Always expend the smaller queue first

if (q1.size() > q2.size())

std::swap(q1, q2);

unordered_set<string> q;

for (string w : q1) {

for (int i = 0; i < l; i++) {

char ch = w[i];

for (int j = 'a'; j <= 'z'; j++) {

w[i] = j;

if (q2.count(w)) return step + 1;

if (!dict.count(w)) continue;

dict.erase(w);

q.insert(w);

}

w[i] = ch;

}

std::swap(q, q1);

}

return 0;

}

};

Java

// Author: Huahua

// Running time: 31 ms (<95.17%)

class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>();

for (String word : wordList) dict.add(word);

if (!dict.contains(endWord)) return 0;

Set<String> q1 = new HashSet<>();

Set<String> q2 = new HashSet<>();

q1.add(beginWord);

q2.add(endWord);

int l = beginWord.length();

int steps = 0;

while (!q1.isEmpty() && !q2.isEmpty()) {

++steps;

if (q1.size() > q2.size()) {

Set<String> tmp = q1;

q1 = q2;

q2 = tmp;

}

Set<String> q = new HashSet<>();

for (String w : q1) {

char[] chs = w.toCharArray();

for (int i = 0; i < l; ++i) {

char ch = chs[i];

for (char c = 'a'; c <= 'z'; ++c) {

chs[i] = c;

String t = new String(chs);

if (q2.contains(t)) return steps + 1;

if (!dict.contains(t)) continue;

dict.remove(t);

q.add(t);

}

chs[i] = ch;

}

q1 = q;

}

return 0;

}

Python

"""

Author: Huahua

Running time: 115 ms (better than 96.84%)

"""

class Solution(object):

def ladderLength(self, beginWord, endWord, wordList):

wordDict = set(wordList)

if endWord not in wordDict: return 0

l = len(beginWord)

s1 = {beginWord}

s2 = {endWord}

wordDict.remove(endWord)

step = 0

while len(s1) > 0 and len(s2) > 0:

step += 1

if len(s1) > len(s2): s1, s2 = s2, s1

s = set()

for w in s1:

new_words = [

w[:i] + t + w[i+1:] for t in string.ascii_lowercase for i in xrange(l)]

for new_word in new_words:

if new_word in s2: return step + 1

if new_word not in wordDict: continue

wordDict.remove(new_word)

s.add(new_word)

s1 = s

return 0

Posts tagged as “word”

花花酱 LeetCode 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Solution 1: Brute Force

C++

花花酱 LeetCode 58. Length of Last Word

Solution:

C++

花花酱 LeetCode 127. Word Ladder

Solution 1: BFS

C++

Java

Solution 2: Bidirectional BFS

C++

Java

Python

Related Problems