search – Page 6 – Huahua’s Tech Road

花花酱 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters

By zxi on October 27, 2019

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Constraints:

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lower case English letters.

Solution: Combination + Bit

Time complexity: O(2^n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxLength(vector<string>& arr) {

vector<int> a;

for (const string& x : arr) {

set<char> s(begin(x), end(x));

if (s.size() != x.length()) continue;

a.push_back(0);

for (char c : x) a.back() |= 1 << (c - 'a');

}

int ans = 0;

function<void(int, int)> dfs = [&](int s, int cur) {

ans = max(ans, __builtin_popcount(cur));

for (int i = s; i < a.size(); ++i)

if ((cur & a[i]) == 0)

dfs(i + 1, cur | a[i]);

};

dfs(0, 0);

return ans;

}

};

Solution 2: DP

Time complexity: O(2^n)
Space complexity: O(2^n)

C++

// Author: Huahua

class Solution {

public:

int maxLength(vector<string>& arr) {

vector<int> a;

for (const string& x : arr) {

int mask = 0;

for (char c : x) mask |= 1 << (c - 'a');

if (__builtin_popcount(mask) != x.length()) continue;

a.push_back(mask);

}

int ans = 0;

vector<int> dp{0};

for (int i = 0; i < a.size(); ++i) {

int size = dp.size();

for (int j = 0; j < size; ++j) {

if (dp[j] & a[i]) continue;

int t = dp[j] | a[i];

dp.push_back(t);

ans = max(ans, __builtin_popcount(t));

}

return ans;

}

};

花花酱 LeetCode 46. Permutations

By zxi on October 2, 2019

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution: DFS

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> permute(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> ans;

vector<int> used(n);

vector<int> path;

function<void(int)> dfs = [&](int d) {

if (d == n) {

ans.push_back(path);

return;

}

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

if (used[i]) continue;

used[i] = 1;

path.push_back(nums[i]);

dfs(d + 1);

path.pop_back();

used[i] = 0;

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 77. Combinations

By zxi on September 30, 2019

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution: DFS

Time complexity: O(C(n, k))
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> combine(int n, int k) {

vector<vector<int>> ans;

vector<int> cur;

function<void(int)> dfs = [&](int s) {

if (cur.size() == k) {

ans.push_back(cur);

return;

}

for (int i = s; i < n; ++i) {

cur.push_back(i + 1);

dfs(i + 1);

cur.pop_back();

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 93. Restore IP Addresses

By zxi on September 30, 2019

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Solution: DFS

The range of valid numbers is [0, 255]

Time complexity: O(3^4)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<string> restoreIpAddresses(string s) {

vector<string> ans;

string ip;

dfs(0, s, ip, ans);

return ans;

}

private:

void dfs(int d, string s, string ip, vector<string> &ans) {

int l = s.length();

if (d == 4) {

if (l == 0) ans.push_back(ip);

return;

}

for (int i = 1; i <= min(3, s[0] == '0' ? 1 : l); i++) {

string ss = s.substr(0, i);

if (i == 3 && stoi(ss) > 255) return;

dfs(d + 1, s.substr(i), ip + (d == 0 ? "" : ".") + ss , ans);

}

};

花花酱 LeetCode 212. Word Search II

By zxi on August 20, 2019

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

All inputs are consist of lowercase letters a-z.
The values of words are distinct.

Solution 1: DFS

Time complexity: O(sum(m*n*4^l))
Space complexity: O(l)

C++

// Author: Huahua, 708 ms, 15.3 MB

class Solution {

public:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

unordered_set<string> unique_words(words.begin(), words.end());

vector<string> ans;

for (const string& word : unique_words)

if (exist(board, word))

ans.push_back(word);

return ans;

}

private:

int w;

int h;

bool exist(vector<vector<char>> &board, string word) {

if (board.size() == 0) return false;

h = board.size();

w = board[0].size();

for (int i = 0 ; i < w; i++)

for (int j = 0 ; j < h; j++)

if (search(board, word, 0, i, j)) return true;

return false;

}

bool search(vector<vector<char>> &board,

const string& word, int d, int x, int y) {

if (x < 0 || x == w || y < 0 || y == h || word[d] != board[y][x])

return false;

// Found the last char of the word

if (d == word.length() - 1)

return true;

char cur = board[y][x];

board[y][x] = '#';

bool found = search(board, word, d + 1, x + 1, y)

|| search(board, word, d + 1, x - 1, y)

|| search(board, word, d + 1, x, y + 1)

|| search(board, word, d + 1, x, y - 1);

board[y][x] = cur;

return found;

}

};

Solution 2: Trie

Store all the words into a trie, search the board using DFS, paths must be in the trie otherwise there is no need to explore.

Time complexity: O(sum(l) + 4^max(l))
space complexity: O(sum(l) + l)

C++

// Author: Huahua, 64 ms, 35.6 MB

class TrieNode {

public:

vector<TrieNode*> nodes;

const string* word;

TrieNode(): nodes(26), word(nullptr) {}

~TrieNode() {

for (auto node : nodes) delete node;

}

};

class Solution {

public:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

TrieNode root;

// Add all the words into Trie.

for (const string& word : words) {

TrieNode* cur = &root;

for (char c : word) {

auto& next = cur->nodes[c - 'a'];

if (!next) next = new TrieNode();

cur = next;

}

cur->word = &word;

}

const int n = board.size();

const int m = board[0].size();

vector<string> ans;

function<void(int, int, TrieNode*)> walk = [&](int x, int y, TrieNode* node) {

if (x < 0 || x == m || y < 0 || y == n || board[y][x] == '#')

return;

const char cur = board[y][x];

TrieNode* next_node = node->nodes[cur - 'a'];

// Pruning, only expend paths that are in the trie.

if (!next_node) return;

if (next_node->word) {

ans.push_back(*next_node->word);

next_node->word = nullptr;

}

board[y][x] = '#';

walk(x + 1, y, next_node);

walk(x - 1, y, next_node);

walk(x, y + 1, next_node);

walk(x, y - 1, next_node);

board[y][x] = cur;

};

// Try all possible pathes.

for (int i = 0 ; i < n; i++)

for (int j = 0 ; j < m; j++)

walk(j, i, &root);

return ans;

}

};

Posts tagged as “search”

花花酱 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters

Solution: Combination + Bit

C++

C++

花花酱 LeetCode 46. Permutations

Solution: DFS

C++

Related Problems

花花酱 LeetCode 77. Combinations

Solution: DFS

C++

Related Problems

花花酱 LeetCode 93. Restore IP Addresses

Solution: DFS

C++

花花酱 LeetCode 212. Word Search II

Solution 1: DFS

C++

Solution 2: Trie

C++