{"id":"c87affcc-86d0-458e-aac3-b4fe1c3f6c62","name":"Word Search Ii","description":"1. Given an m x n board of characters and a list of strings words, return all words present on the board.\r\n2. Word must be made from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.\r\n\r\nYou can return word's in any order.","inputFormat":"n\r\nm\r\nstr1\r\nstr2\r\n... n string's each of length m\r\nlen count of words\r\nstr1\r\nstr2\r\n... len number of string's.","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= m, n &lt;= 12\r\n2. 1 &lt;= words.length &lt;= 3 * 10^4\r\n3. 1 &lt;= words[i].length &lt;= 10\r\n4. words[i] consists of lowercase English letters.\r\n5. All the strings of words are unique.","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nclass Node {\n public:\n vector<Node*>childs;\n string str;\n int count;\n Node(){\n childs.resize(26,nullptr);\n \n }\n};\n\nvoid insert(Node *curr, string s) {\n\n \n }\n\nvoid dfs(vector<vector<char>>&board, int i, int j, Node *root, vector<string>&ans, vector<vector<bool>>&visited)\n{\n \n } \n \n \nvector<string> findWords(vector<vector<char>>&board, vector<string> &words) {\n\n \n}\n\nint main(){\n int n,m;\n cin>>n>>m;\n vector<vector<char>>board;\n \n for(int i=1;i<=m;i++){\n string s;\n cin>>s;\n vector<char>temp;\n for(int j=0;j<s.length();j++){\n temp.push_back(s[j]);\n }\n \n board.push_back(temp);\n }\n \n \n int count;\n cin>>count;\n \n \n vector<string>words(count);\n for(int i=0;i<count;i++){\n string temp;\n cin>>temp;\n words.push_back(temp);\n }\n \n \n \n \n vector<string>result=findWords(board,words);\n sort(result.begin(),result.end());\n cout<<\"[\";\n \n for(int i=0;i<result.size();i++){\n if(i==result.size()-1){\n cout<<result[i];\n }else{\n cout<<result[i]<<\", \";\n }\n }\n cout<<\"]\";\n}"},"java":{"code":"import java.io.*;\r\nimport java.net.Inet4Address;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static ArrayList<String> findWords(char[][] board, String[] words) {\r\n return null;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n int m = Integer.parseInt(read.readLine());\r\n char[][]board = new char[n][];\r\n for (int i = 0; i < n; i++) {\r\n board[i] = read.readLine().trim().toCharArray();\r\n }\r\n int count = Integer.parseInt(read.readLine());\r\n String words[] = new String[count];\r\n for (int i = 0; i < count; i++) {\r\n words[i] = read.readLine();\r\n }\r\n\r\n ArrayList<String> result = findWords(board, words);\r\n Collections.sort(result);\r\n System.out.println(result);\r\n\r\n }\r\n}\r\n"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"4\r\n4\r\noaan\r\netae\r\nihkr\r\niflv\r\n5\r\noath\r\npea\r\neat\r\neatat\r\nrain\r\n","sampleOutput":"[eat, oath]\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"4b4725b5-4896-4b68-aae2-03ea1e2ecbb2","name":"Trie For Intermediate","slug":"trie-for-intermediate-9996","type":0},{"id":"556b11fd-8cb4-48f9-8d59-e05e114dde68","name":"Word Search Ii MCQ","slug":"word-search-ii-mcq","type":0},{"id":"a6d184da-1c6d-4164-a4b9-a313ab6c6672","name":"Word Search Ii","slug":"word-search-ii","type":1}],"next":null,"prev":null}}

Word Search Ii

1. Given an m x n board of characters and a list of strings words, return all words present on the board. 2. Word must be made from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. You can return word's in any order.

{"id":"c87affcc-86d0-458e-aac3-b4fe1c3f6c62","name":"Word Search Ii","description":"1. Given an m x n board of characters and a list of strings words, return all words present on the board.\r\n2. Word must be made from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.\r\n\r\nYou can return word's in any order.","inputFormat":"n\r\nm\r\nstr1\r\nstr2\r\n... n string's each of length m\r\nlen count of words\r\nstr1\r\nstr2\r\n... len number of string's.","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= m, n &lt;= 12\r\n2. 1 &lt;= words.length &lt;= 3 * 10^4\r\n3. 1 &lt;= words[i].length &lt;= 10\r\n4. words[i] consists of lowercase English letters.\r\n5. All the strings of words are unique.","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nclass Node {\n public:\n vector<Node*>childs;\n string str;\n int count;\n Node(){\n childs.resize(26,nullptr);\n \n }\n};\n\nvoid insert(Node *curr, string s) {\n\n \n }\n\nvoid dfs(vector<vector<char>>&board, int i, int j, Node *root, vector<string>&ans, vector<vector<bool>>&visited)\n{\n \n } \n \n \nvector<string> findWords(vector<vector<char>>&board, vector<string> &words) {\n\n \n}\n\nint main(){\n int n,m;\n cin>>n>>m;\n vector<vector<char>>board;\n \n for(int i=1;i<=m;i++){\n string s;\n cin>>s;\n vector<char>temp;\n for(int j=0;j<s.length();j++){\n temp.push_back(s[j]);\n }\n \n board.push_back(temp);\n }\n \n \n int count;\n cin>>count;\n \n \n vector<string>words(count);\n for(int i=0;i<count;i++){\n string temp;\n cin>>temp;\n words.push_back(temp);\n }\n \n \n \n \n vector<string>result=findWords(board,words);\n sort(result.begin(),result.end());\n cout<<\"[\";\n \n for(int i=0;i<result.size();i++){\n if(i==result.size()-1){\n cout<<result[i];\n }else{\n cout<<result[i]<<\", \";\n }\n }\n cout<<\"]\";\n}"},"java":{"code":"import java.io.*;\r\nimport java.net.Inet4Address;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static ArrayList<String> findWords(char[][] board, String[] words) {\r\n return null;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n int m = Integer.parseInt(read.readLine());\r\n char[][]board = new char[n][];\r\n for (int i = 0; i < n; i++) {\r\n board[i] = read.readLine().trim().toCharArray();\r\n }\r\n int count = Integer.parseInt(read.readLine());\r\n String words[] = new String[count];\r\n for (int i = 0; i < count; i++) {\r\n words[i] = read.readLine();\r\n }\r\n\r\n ArrayList<String> result = findWords(board, words);\r\n Collections.sort(result);\r\n System.out.println(result);\r\n\r\n }\r\n}\r\n"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"4\r\n4\r\noaan\r\netae\r\nihkr\r\niflv\r\n5\r\noath\r\npea\r\neat\r\neatat\r\nrain\r\n","sampleOutput":"[eat, oath]\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"4b4725b5-4896-4b68-aae2-03ea1e2ecbb2","name":"Trie For Intermediate","slug":"trie-for-intermediate-9996","type":0},{"id":"556b11fd-8cb4-48f9-8d59-e05e114dde68","name":"Word Search Ii MCQ","slug":"word-search-ii-mcq","type":0},{"id":"a6d184da-1c6d-4164-a4b9-a313ab6c6672","name":"Word Search Ii","slug":"word-search-ii","type":1}],"next":null,"prev":null}}
plane

Editor


Loading...

Word Search Ii

hard

1. Given an m x n board of characters and a list of strings words, return all words present on the board. 2. Word must be made from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. You can return word's in any order.

Constraints

1. 1 <= m, n <= 12 2. 1 <= words.length <= 3 * 10^4 3. 1 <= words[i].length <= 10 4. words[i] consists of lowercase English letters. 5. All the strings of words are unique.

Format

Input

n m str1 str2 ... n string's each of length m len count of words str1 str2 ... len number of string's.

Output

Output is managed for you

Example

Sample Input

4 4 oaan etae ihkr iflv 5 oath pea eat eatat rain

Sample Output

[eat, oath]

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode