Posts tagged as “string”

花花酱 LeetCode 127. Word Ladder

By zxi on September 25, 2017

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

Related Problems

花花酱 LeetCode 680. Valid Palindrome II

By zxi on September 17, 2017

Problem:

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

1 2	Input: "aba" Output: True

Example 2:

Input: "abca"

Output: True

Explanation: You could delete the character 'c'.

Note:

The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Idea:

Greedy, delete the first unmatched char

Time complexity

O(n)

Solution:

// Author: Huahua

// Running time: 118 ms

class Solution {

public:

bool validPalindrome(const string& s) {

int l = -1;

int r = s.length();

while (++l < --r)

if (s[l] != s[r])

return isPalindrome(s, l+1, r)

|| isPalindrome(s, l, r-1);

return true;

}

private:

bool isPalindrome(const string& s, int l, int r) {

while (l < r)

if (s[l++] != s[r--]) return false;

return true;

}

};

花花酱 LeetCode 241. Different Ways to Add Parentheses

By zxi on September 3, 2017

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1".

1 2	((2-1)-1) = 0 (2-(1-1)) = 2

Output: [0, 2]

Example 2:

Input: "2*3-4*5"

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Solution:

Running time: 3ms

C++

// Author: Huahua

namespace huahua {

int add(int a, int b) { return a+b; }

int minus(int a, int b) { return a-b; }

int multiply(int a, int b) { return a*b; }

} // namespace huahua

class Solution {

public:

vector<int> diffWaysToCompute(string input) {

return ways(input);

}

private:

const vector<int>& ways(const string& input) {

// Already solved, return the answer

if(m_.count(input)) return m_[input];

// Array for answer of input

vector<int> ans;

// Break the expression at every operator

for(int i=0;i<input.length();++i) {

char op = input[i];

// Split the input by an op

if(op=='+' || op=='-' || op=='*') {

const string left = input.substr(0, i);

const string right = input.substr(i+1);

// Get the solution of left/right sub-expressions

const vector<int>& l = ways(left);

const vector<int>& r = ways(right);

std::function<int(int,int)> f;

switch(op) {

case '+': f = huahua::add; break;

case '-': f = huahua::minus; break;

case '*': f = huahua::multiply; break;

}

// Combine the solution

for(int a : l)

for(int b : r)

ans.push_back(f(a,b));

}

// Single number, e.g. s = "3"

if(ans.empty())

ans.push_back(std::stoi(input));

// memorize the answer for input

m_[input].swap(ans);

return m_[input];

}

unordered_map<string, vector<int>> m_;

};

Python3

# Author: Huahua, 44 ms

class Solution:

def diffWaysToCompute(self, input):

ops = {'+': lambda x, y: x + y,

'-': lambda x, y: x - y,

'*': lambda x, y: x * y}

def ways(s):

ans = []

for i in range(len(s)):

if s[i] in "+-*":

ans += [ops[s[i]](l, r) for l, r in itertools.product(ways(s[0:i]), ways(s[i+1:]))]

if not ans: ans.append(int(s))

return ans

return ways(input)

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Idea:

Time complexity O(n^2)

Space complexity O(n^2)

Solutions:

C++

// Author: Huahua

class Solution {

public:

bool wordBreak(string s, vector<string>& wordDict) {

// Create a hashset of words for fast query.

unordered_set<string> dict(wordDict.cbegin(), wordDict.cend());

// Query the answer of the original string.

return wordBreak(s, dict);

}

bool wordBreak(const string& s, const unordered_set<string>& dict) {

// In memory, directly return.

if(mem_.count(s)) return mem_[s];

// Whole string is a word, memorize and return.

if(dict.count(s)) return mem_[s]=true;

// Try every break point.

for(int j=1;j<s.length();j++) {

const string left = s.substr(0,j);

const string right = s.substr(j);

// Find the solution for s.

if(dict.count(right) && wordBreak(left, dict))

return mem_[s]=true;

}

// No solution for s, memorize and return.

return mem_[s]=false;

}

private:

unordered_map<string, bool> mem_;

};

C++ V2 without using dict. Updated: 1/9/2018

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

bool wordBreak(string s, vector<string>& wordDict) {

// Mark evert word as breakable.

for (const string& word : wordDict)

mem_.emplace(word, true);

// Query the answer of the original string.

return wordBreak(s);

}

bool wordBreak(const string& s) {

// In memory, directly return.

if (mem_.count(s)) return mem_[s];

// Try every break point.

for (int j = 1; j < s.length(); j++) {

auto it = mem_.find(s.substr(j));

// Find the solution for s.

if (it != mem_.end() && it->second && wordBreak(s.substr(0, j)))

return mem_[s] = true;

}

// No solution for s, memorize and return.

return mem_[s] = false;

}

private:

unordered_map<string, bool> mem_;

};

Java

// Author: Huahua

// Runtime: 13 ms

class Solution {

public boolean wordBreak(String s, List<String> wordDict) {

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

Map<String, Boolean> mem = new HashMap<String, Boolean>();

return wordBreak(s, mem, dict);

}

private boolean wordBreak(String s,

Map<String, Boolean> mem,

Set<String> dict) {

if (mem.containsKey(s)) return mem.get(s);

if (dict.contains(s)) {

mem.put(s, true);

return true;

}

for (int i = 1; i < s.length(); ++i) {

if (dict.contains(s.substring(i)) && wordBreak(s.substring(0, i), mem, dict)) {

mem.put(s, true);

return true;

}

mem.put(s, false);

return false;

}

Python

"""

Author: Huahua

Runtime: 42 ms

"""

class Solution(object):

def wordBreak(self, s, wordDict):

def canBreak(s, m, wordDict):

if s in m: return m[s]

if s in wordDict:

m[s] = True

return True

for i in range(1, len(s)):

r = s[i:]

if r in wordDict and canBreak(s[0:i], m, wordDict):

m[s] = True

return True

m[s] = False

return False

return canBreak(s, {}, set(wordDict))

花花酱 LeetCode 451. Sort Characters By Frequency

By zxi on March 18, 2017

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:

"tree"

Output:

"eert"

Explanation:

'e' appears twice while 'r' and 't' both appear once.

So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:

"cccaaa"

Output:

"cccaaa"

Explanation:

Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.

Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:

"Aabb"

Output:

"bbAa"

Explanation:

"bbaA" is also a valid answer, but "Aabb" is incorrect.

Note that 'A' and 'a' are treated as two different characters.

Solution:

class Solution {

public:

string frequencySort(string s) {

map<char, int> f;

for(char c:s) ++f[c];

vector<pair<int,char>> v;

for(auto& kv : f)

v.push_back({kv.second, kv.first});

sort(v.rbegin(), v.rend());

stringstream ans;

for(auto& kv : v)

ans << string(kv.first, kv.second);

return ans.str();

}

};

Posts tagged as “string”

花花酱 LeetCode 127. Word Ladder

Solution 1: BFS

C++

Java

Solution 2: Bidirectional BFS

C++

Java

Python

Related Problems

花花酱 LeetCode 680. Valid Palindrome II

花花酱 LeetCode 241. Different Ways to Add Parentheses

C++

Python3

花花酱 Leetcode 139. Word Break

Problem

Idea:

Solutions:

花花酱 LeetCode 451. Sort Characters By Frequency