commit 531e5766e93dcfd2527221a5296382e575d67cf7
parent 02c169ae54d6f01f54881bd5be3af25073b9165a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 21 Oct 2024 18:39:54 +0200
5 Random Problems
Diffstat:
6 files changed, 179 insertions(+), 0 deletions(-)
diff --git a/Problems/0065.cpp b/Problems/0065.cpp
@@ -0,0 +1,49 @@
+class Solution {
+ using it_t = string::const_iterator;
+
+ static bool validSign(it_t &pos, const it_t &end) {
+ if (*pos == '-' || *pos == '+') {
+ pos++;
+ if (find(pos, end, '-') != end || find(pos, end, '+') != end) {
+ return false;
+ }
+ }
+
+ return pos != end;
+ }
+
+ static bool validDigit(const it_t &pos, const it_t &end) {
+ return all_of(pos, end, [](char c) { return isdigit(c); });
+ }
+
+ static bool isDecimal(const string &s) {
+ auto pos = begin(s);
+
+ if (!validSign(pos, end(s))) return false;
+ if (string(pos, end(s)) == ".") return false;
+
+ auto dot = find(pos, end(s), '.');
+ return validDigit(pos, dot) && validDigit(dot + 1, end(s));
+ }
+
+ static bool isInteger(const string &s) {
+ auto pos = begin(s);
+ if (!validSign(pos, end(s))) return false;
+ return validDigit(pos, end(s));
+ }
+
+ public:
+ bool isNumber(const string &s) const {
+ auto e = s.find('e'), E = s.find('E');
+
+ if (E != string::npos) swap(e, E);
+ if (e != string::npos) {
+ const string first = s.substr(0, e);
+ const string second = s.substr(e + 1);
+ return !first.empty() && !second.empty() && isInteger(second) &&
+ (isDecimal(first) || isInteger(first));
+ }
+
+ return isDecimal(s) || isInteger(s);
+ }
+};
diff --git a/Problems/0115.cpp b/Problems/0115.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ static int dp[1001][1001];
+
+ static int rec(const string &s, const string &t, int check, int goal) {
+ if (goal == size(t)) return 1;
+ if (check == size(s)) return 0;
+ if (dp[check][goal] != -1) return dp[check][goal];
+
+ int res = rec(s, t, check + 1, goal);
+ if (s[check] == t[goal]) res += rec(s, t, check + 1, goal + 1);
+ return dp[check][goal] = res;
+ }
+
+ public:
+ int numDistinct(const string &s, const string &t) const {
+ memset(dp, 0xFF, sizeof(dp));
+ return rec(s, t, 0, 0);
+ }
+};
+
+int Solution::dp[1001][1001];
diff --git a/Problems/0126.cpp b/Problems/0126.cpp
@@ -0,0 +1,61 @@
+class Solution {
+ unordered_map<string, vector<string>> adj;
+ vector<vector<string>> res;
+ vector<string> state;
+
+ void dfs(const string &crnt, int lvl) {
+ if (lvl == 0) {
+ res.push_back(state);
+ return;
+ }
+
+ for (const auto &word : adj[crnt]) {
+ state[lvl - 1] = word;
+ dfs(word, lvl - 1);
+ }
+ }
+
+ public:
+ vector<vector<string>> findLadders(const string &beginWord, const string &endWord,
+ vector<string> &wordList) {
+ unordered_set<string> set(begin(wordList), end(wordList));
+ unordered_set<string> seen;
+ queue<string> q;
+
+ q.push(beginWord);
+ for (int lvl = 1; !q.empty(); lvl++) {
+ for (int k = size(q); k > 0; k--) {
+ const auto root = q.front();
+ q.pop();
+
+ cout << root << endl;
+ if (root == endWord) {
+ state = vector<string>(lvl);
+ state[lvl - 1] = endWord;
+ dfs(root, lvl - 1);
+ return res;
+ }
+
+ auto crnt = root;
+ for (int i = 0; i < size(crnt); i++) {
+ const char og = crnt[i];
+ for (char c = 'a'; c <= 'z'; c++) {
+ crnt[i] = c;
+ if (!set.count(crnt)) continue;
+ if (!seen.count(crnt)) {
+ seen.emplace(crnt);
+ q.push(crnt);
+ }
+ adj[crnt].push_back(root);
+ }
+ crnt[i] = og;
+ }
+ }
+
+ for (const auto &word : seen)
+ set.erase(word);
+ }
+
+ return {};
+ }
+};
diff --git a/Problems/0132.cpp b/Problems/0132.cpp
@@ -0,0 +1,22 @@
+class Solution {
+ public:
+ int minCut(const string &s) const {
+ static bool dp[2001][2001];
+ static int cut[2001];
+ const int n = s.size();
+
+ memset(dp, 0x00, sizeof(dp));
+ for (int i = 0; i < n; i++) {
+ int mini = i;
+ for (int j = 0; j <= i; j++) {
+ if (s[i] == s[j] && (i - j < 3 || dp[i - 1][j + 1])) {
+ mini = j == 0 ? 0 : min(mini, cut[j - 1] + 1);
+ dp[i][j] = true;
+ }
+ }
+ cut[i] = mini;
+ }
+
+ return cut[n - 1];
+ }
+};
diff --git a/Problems/0147.cpp b/Problems/0147.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ public:
+ ListNode *insertionSortList(ListNode *head) const {
+ ListNode dummy(-1, head);
+ ListNode *prev = &dummy, *crnt = head;
+
+ for (; crnt; prev = crnt, crnt = crnt->next) {
+ if (prev->val <= crnt->val) continue;
+ for (ListNode *p = &dummy, *c = dummy.next; p != prev; p = c, c = c->next) {
+ if (c->val <= crnt->val) continue;
+ prev->next = crnt->next;
+ crnt->next = p->next;
+ p->next = crnt;
+ crnt = prev;
+ break;
+ }
+ }
+
+ return dummy.next;
+ }
+};
diff --git a/README.md b/README.md
@@ -88,6 +88,7 @@ for solving problems.
| 0062 | Medium | [Unique Paths](Problems/0062.cpp) |
| 0063 | Medium | [Unique Paths II](Problems/0063.cpp) |
| 0064 | Medium | [Minimum Path Sum](Problems/0064.cpp) |
+| 0065 | Hard | [Valid Number](Problems/0065.cpp) |
| 0066 | Easy | [Plus One](Problems/0066.cpp) |
| 0067 | Easy | [Add Binary](Problems/0067.cpp) |
| 0068 | Hard | [Text Justification](Problems/0068.cpp) |
@@ -137,6 +138,7 @@ for solving problems.
| 0112 | Easy | [Path Sum](Problems/0112.cpp) |
| 0113 | Medium | [Path Sum II](Problems/0113.cpp) |
| 0114 | Medium | [Flatten Binary Tree to Linked List](Problems/0114.cpp) |
+| 0115 | Hard | [Distinct Subsequences](Problems/0115.cpp) |
| 0116 | Medium | [Populating Next Right Pointers in Each Node](Problems/0116.cpp) |
| 0117 | Medium | [Populating Next Right Pointers in Each Node II](Problems/0117.cpp) |
| 0118 | Easy | [Pascal's Triangle](Problems/0118.cpp) |
@@ -147,11 +149,13 @@ for solving problems.
| 0123 | Hard | [Best Time to Buy and Sell Stock III](Problems/0123.cpp) |
| 0124 | Hard | [Binary Tree Maximum Path Sum](Problems/0124.cpp) |
| 0125 | Easy | [Valid Palindrome](Problems/0125.cpp) |
+| 0126 | Hard | [Word Ladder II](Problems/0126.cpp) |
| 0127 | Hard | [Word Ladder](Problems/0127.cpp) |
| 0128 | Medium | [Longest Consecutive Sequence](Problems/0128.cpp) |
| 0129 | Medium | [Sum Root to Leaf Numbers](Problems/0129.cpp) |
| 0130 | Medium | [Surrounded Regions](Problems/0130.cpp) |
| 0131 | Medium | [Palindrome Partitioning](Problems/0131.cpp) |
+| 0132 | Hard | [Palindrome Partitioning II](Problems/0132.cpp) |
| 0133 | Medium | [Clone Graph](Problems/0133.cpp) |
| 0134 | Medium | [Gas Station](Problems/0134.cpp) |
| 0135 | Hard | [Candy](Problems/0135.cpp) |
@@ -166,6 +170,7 @@ for solving problems.
| 0144 | Medium | [Binary Tree Preorder Traversal](Problems/0144.cpp) |
| 0145 | Easy | [Binary Tree Postorder Traversal](Problems/0145.cpp) |
| 0146 | Medium | [LRU Cache](Problems/0146.cpp) |
+| 0147 | Medium | [Insertion Sort List](Problems/0147.cpp) |
| 0148 | Medium | [Sort List](Problems/0148.cpp) |
| 0149 | Hard | [Max Points on a Line](Problems/0149.cpp) |
| 0150 | Medium | [Evaluate Reverse Polish Notation](Problems/0150.cpp) |
