Category Archives: Backtrack

Implement strStr()

Implement strStr(). Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack. C++: 01 class Solution { 02 public: 03     char *strStr(char *haystack, char *needle) { 04         // Start typing … Continue reading

Posted in Backtrack, String | Leave a comment

Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. A partially filled sudoku which is valid. C++: 01 class Solution { 02 public: 03  … Continue reading

Posted in Array and linked list, Backtrack | Leave a comment

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character ‘.’. You may assume that there will be only one unique solution. A sudoku puzzle… …and its solution numbers marked in … Continue reading

Posted in Array and linked list, Backtrack | Leave a comment

N-Queens II

Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. C++: 01 void totalNQueensHelper(int n, vector<int>& cur, int& result) 02 { 03     int m=cur.size(); 04     if(m==n) 05     { 06        … Continue reading

Posted in Array and linked list, Backtrack | Leave a comment

N-Queens

The n-queens puzzle is the problem of placing n queens on an n�n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a … Continue reading

Posted in Backtrack, Recursive | Leave a comment

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 … Continue reading

Posted in Backtrack, String | Leave a comment

N-Queens II

Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. C++: 01 void solve(vector<int>& cur, int n, int& cnt) 02 { 03     int m=cur.size(); 04     if(m==n){ 05         cnt++; 06    … Continue reading

Posted in Array and linked list, Backtrack | Leave a comment