loading...

Daily Coding Challenge #72

wingkwong profile image Wing-Kam ・2 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // recursive approach
        // [1,2,6,3,4,5,6]
        // 6
        // head->val = 6
        // head->val = 5
        // head->val = 4
        // head->val = 3
        // head->val = 6
        // head->val = 2
        // head->val = 1
        if(head==NULL) return NULL;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};



/*
Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can 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.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.


Constraints:

board and word consists only of lowercase and uppercase English letters.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
*/

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        r = (int)board.size();
        c = (int)board[0].size();
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                // find the first char
                if(dfs(i,j,board,word,0)) return true;
            }
        }
        return false;
    }
private:
    int r,c;
    // typical dfs approach
    bool dfs(int i, int j, vector<vector<char>>& board, string& word, int k){
        // base cases
        if(i<0||i>=r||j<0||j>=c||board[i][j]!=word[k]) return false;
        // ans found
        if(k==word.size()-1) return true;
        // mark board[i][j] to '*' to represent this char has been visited
        char cur = board[i][j];
        board[i][j] = '*';
        // search for four directions
        bool found = dfs(i-1,j,board,word,k+1)
                    || dfs(i+1,j,board,word,k+1)
                    || dfs(i,j-1,board,word,k+1)
                    || dfs(i,j+1,board,word,k+1);
        // reset. mark it not visited 
        board[i][j] = cur;
        // return if it is found or not
        return found;
    }
};

static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

🏆 A Collection of my LeetCode Solutions with Explanations 🏆

GitHub logo wingkwong / hackerrank

🏆 A Collection of my HackerRank Solutions with Explanations 🏆

GitHub logo wingkwong / codeforces

🏆 A Collection of my Codeforces Solutions with Explanations 🏆

GitHub logo wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

markdown guide