g*e
2 楼
是吧 还需要一个矩阵记录某个位置是否已经走过了
s*n
3 楼
SURE, IT IS RIGHT..
g*y
4 楼
public class Boggle {
private final int N = 5;
private HashSet m_words;
public Boggle() {
m_words = new HashSet();
}
public static void main(String[] args) {
String[] str = new String[]{
"AEBOF", "TSUVW", "RFOEG", "RSOFI", "PQWRE"
};
new Boggle().run(str);
}
public void run(String[] str) {
char[][] cs = new char[N][N];
boolean[][] used = new boolean[N][N];
m_words.clear();
Trie trie = new Trie();
String dictionary = FileHelper.readFile("src/test/resources/english-
dict.txt");
for (String word : dictionary.split("\n")) {
if (word.length() > 0) trie.addWord(word.toLowerCase());
}
for (int i=0; i cs[i] = str[i].toLowerCase().toCharArray();
}
for (int i=0; i for (int j=0; j dfs("", cs, i, j, used, trie);
}
}
System.out.println("Find " + m_words.size() + " words.");
}
private void dfs(String cur, char[][] cs, int i, int j, boolean[][] used
, Trie node) {
if (i<0 || i>N-1 || j<0 || j>N-1 || used[i][j]) return;
String next = cur + cs[i][j];
node = node.getNode(cs[i][j]);
if (node == null) return;
used[i][j] = true;
if (node.isWord() && !m_words.contains(next)) {
m_words.add(next);
System.out.println(next);
}
dfs(next, cs, i-1, j-1, used, node);
dfs(next, cs, i, j-1, used, node);
dfs(next, cs, i+1, j-1, used, node);
dfs(next, cs, i-1, j, used, node);
dfs(next, cs, i+1, j, used, node);
dfs(next, cs, i-1, j+1, used, node);
dfs(next, cs, i, j+1, used, node);
dfs(next, cs, i+1, j+1, used, node);
used[i][j] = false;
}
}
private final int N = 5;
private HashSet
public Boggle() {
m_words = new HashSet
}
public static void main(String[] args) {
String[] str = new String[]{
"AEBOF", "TSUVW", "RFOEG", "RSOFI", "PQWRE"
};
new Boggle().run(str);
}
public void run(String[] str) {
char[][] cs = new char[N][N];
boolean[][] used = new boolean[N][N];
m_words.clear();
Trie trie = new Trie();
String dictionary = FileHelper.readFile("src/test/resources/english-
dict.txt");
for (String word : dictionary.split("\n")) {
if (word.length() > 0) trie.addWord(word.toLowerCase());
}
for (int i=0; i
}
for (int i=0; i
}
}
System.out.println("Find " + m_words.size() + " words.");
}
private void dfs(String cur, char[][] cs, int i, int j, boolean[][] used
, Trie node) {
if (i<0 || i>N-1 || j<0 || j>N-1 || used[i][j]) return;
String next = cur + cs[i][j];
node = node.getNode(cs[i][j]);
if (node == null) return;
used[i][j] = true;
if (node.isWord() && !m_words.contains(next)) {
m_words.add(next);
System.out.println(next);
}
dfs(next, cs, i-1, j-1, used, node);
dfs(next, cs, i, j-1, used, node);
dfs(next, cs, i+1, j-1, used, node);
dfs(next, cs, i-1, j, used, node);
dfs(next, cs, i+1, j, used, node);
dfs(next, cs, i-1, j+1, used, node);
dfs(next, cs, i, j+1, used, node);
dfs(next, cs, i+1, j+1, used, node);
used[i][j] = false;
}
}
l*a
5 楼
a little optimization
for(int m=-1;m<=1;m++)
for(int n=-1;n<=1;n++)
{
if(m==0&&n==0)continue;
dfs(...,i+m,j+n,,,,,);
}
【在 g**********y 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: public class Boggle {
: private final int N = 5;
: private HashSet m_words;
:
: public Boggle() {
: m_words = new HashSet();
: }
:
: public static void main(String[] args) {
: String[] str = new String[]{
for(int m=-1;m<=1;m++)
for(int n=-1;n<=1;n++)
{
if(m==0&&n==0)continue;
dfs(...,i+m,j+n,,,,,);
}
【在 g**********y 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: public class Boggle {
: private final int N = 5;
: private HashSet
:
: public Boggle() {
: m_words = new HashSet
: }
:
: public static void main(String[] args) {
: String[] str = new String[]{
f*t
6 楼
#include
#include
#include
#define ENTRYNOTFOUND 0
#define ENTRYFOUND 1
#define NOTCOMPLETE 2
struct Trie;
void FindWords(Trie *root);
struct Trie
{
Trie();
~Trie();
Trie *children[26];
bool isEnd;
};
Trie::Trie()
{
for(int i = 0; i < 26; i++)
children[i] = NULL;
isEnd = false;
}
Trie::~Trie()
{
for(int i = 0; i < 26; i++) {
if(children[i]) {
delete children[i];
children[i] = NULL;
}
}
}
void TrieInsert(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid line\n");
return;
}
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index] == NULL) {
cur->children[index] = new Trie();
}
cur = cur->children[index];
str++;
}
if(cur != root)
cur->isEnd = true;
}
int TrieSearch(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid string!\n");
return ENTRYNOTFOUND;
}
printf("Looking for word %s\n", str);
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index]) {
cur = cur->children[index];
str++;
}
else
return ENTRYNOTFOUND;
}
if(cur != root && cur->isEnd)
return ENTRYFOUND;
else
return NOTCOMPLETE;
}
int main()
{
Trie *root = new Trie();
FILE *fp = fopen("dictionary.txt", "r");
if(!fp) {
printf("Cannot find dictionary file\n");
exit(-1);
}
char buff[32];
int count = 0;
while(fgets(buff, 31, fp) != NULL) {
TrieInsert(root, buff);
memset(buff, 0, 32);
count++;
}
fclose(fp);
printf("Loaded %d words\n", count);
FindWords(root);
delete root;
return 0;
}
#define WIDTH 4
#define HEIGHT 4
bool isValidIndex(int x, int y, bool used[HEIGHT][WIDTH])
{
if(x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT && !used[y][x])
return true;
else
return false;
}
void dfsWord(Trie *root, char *buff, int buffidx, char matrix[HEIGHT][WIDTH]
, bool used[HEIGHT][WIDTH], int x, int y)
{
/*
if(buffidx > 0)
printf("Current buffer: %s\n", buff);
*/
buff[buffidx] = matrix[y][x];
used[y][x] = true;
int status = TrieSearch(root, buff);
if(status != ENTRYNOTFOUND) {
if(status == ENTRYFOUND)
printf("Found word: %s\n", buff);
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
if(isValidIndex(x-1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y-1);
if(isValidIndex(x, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y-1);
if(isValidIndex(x+1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y-1);
if(isValidIndex(x+1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y);
if(isValidIndex(x+1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y+1);
if(isValidIndex(x, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y+1);
if(isValidIndex(x-1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y+1);
}
buff[buffidx] = 0;
used[y][x] = false;
}
void FindWords(Trie *root)
{
char matrix[HEIGHT][WIDTH] = {
{'t', 'e', 'g', 's'},
{'r', 'e', 'i', 't'},
{'n', 'i', 'f', 'o'},
{'g', 'l', 'k', 'c'},
};
bool used[HEIGHT][WIDTH];
for(int i = 0; i < HEIGHT; i++) {
for(int j = 0; j < WIDTH; j++) {
used[i][j] = false;
}
}
int tempx, tempy;
char buff[32];
int buffidx;
bool noValidChoice;
for(int y = 0; y < HEIGHT; y++) {
for(int x = 0; x < WIDTH; x++) {
memset(buff, 0, 32);
buffidx = 0;
dfsWord(root, buff, buffidx, matrix, used, x, y);
}
}
}
#include
#include
#define ENTRYNOTFOUND 0
#define ENTRYFOUND 1
#define NOTCOMPLETE 2
struct Trie;
void FindWords(Trie *root);
struct Trie
{
Trie();
~Trie();
Trie *children[26];
bool isEnd;
};
Trie::Trie()
{
for(int i = 0; i < 26; i++)
children[i] = NULL;
isEnd = false;
}
Trie::~Trie()
{
for(int i = 0; i < 26; i++) {
if(children[i]) {
delete children[i];
children[i] = NULL;
}
}
}
void TrieInsert(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid line\n");
return;
}
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index] == NULL) {
cur->children[index] = new Trie();
}
cur = cur->children[index];
str++;
}
if(cur != root)
cur->isEnd = true;
}
int TrieSearch(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid string!\n");
return ENTRYNOTFOUND;
}
printf("Looking for word %s\n", str);
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index]) {
cur = cur->children[index];
str++;
}
else
return ENTRYNOTFOUND;
}
if(cur != root && cur->isEnd)
return ENTRYFOUND;
else
return NOTCOMPLETE;
}
int main()
{
Trie *root = new Trie();
FILE *fp = fopen("dictionary.txt", "r");
if(!fp) {
printf("Cannot find dictionary file\n");
exit(-1);
}
char buff[32];
int count = 0;
while(fgets(buff, 31, fp) != NULL) {
TrieInsert(root, buff);
memset(buff, 0, 32);
count++;
}
fclose(fp);
printf("Loaded %d words\n", count);
FindWords(root);
delete root;
return 0;
}
#define WIDTH 4
#define HEIGHT 4
bool isValidIndex(int x, int y, bool used[HEIGHT][WIDTH])
{
if(x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT && !used[y][x])
return true;
else
return false;
}
void dfsWord(Trie *root, char *buff, int buffidx, char matrix[HEIGHT][WIDTH]
, bool used[HEIGHT][WIDTH], int x, int y)
{
/*
if(buffidx > 0)
printf("Current buffer: %s\n", buff);
*/
buff[buffidx] = matrix[y][x];
used[y][x] = true;
int status = TrieSearch(root, buff);
if(status != ENTRYNOTFOUND) {
if(status == ENTRYFOUND)
printf("Found word: %s\n", buff);
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
if(isValidIndex(x-1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y-1);
if(isValidIndex(x, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y-1);
if(isValidIndex(x+1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y-1);
if(isValidIndex(x+1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y);
if(isValidIndex(x+1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y+1);
if(isValidIndex(x, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y+1);
if(isValidIndex(x-1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y+1);
}
buff[buffidx] = 0;
used[y][x] = false;
}
void FindWords(Trie *root)
{
char matrix[HEIGHT][WIDTH] = {
{'t', 'e', 'g', 's'},
{'r', 'e', 'i', 't'},
{'n', 'i', 'f', 'o'},
{'g', 'l', 'k', 'c'},
};
bool used[HEIGHT][WIDTH];
for(int i = 0; i < HEIGHT; i++) {
for(int j = 0; j < WIDTH; j++) {
used[i][j] = false;
}
}
int tempx, tempy;
char buff[32];
int buffidx;
bool noValidChoice;
for(int y = 0; y < HEIGHT; y++) {
for(int x = 0; x < WIDTH; x++) {
memset(buff, 0, 32);
buffidx = 0;
dfsWord(root, buff, buffidx, matrix, used, x, y);
}
}
}
相关阅读
background调查的是找你提供的联系人,还是直接电话以前单位的请教 contingent offer学校挂身份 (转载)填写H1b的LCA时Period of intended employment 的begin date填几号啊?面试时提及之前在该公司的面试是plus吗?求问一道数组shuffle的问题求一个面试题解答。。求暑期实习内推,必有重谢![update]如何跟现在的老板谈reference没看懂leetcode大牛关于一道概率题的答案offer 选择 (转载)高通电面的问题网投简历没什么用呀吐槽一下我的微软实习想不到啊想不到summer找工作的话,会不会opening比较少?LCA 7天处理时间,是工作日还是,calander 日呀?电梯设计题墙街某IB招IT(三次更新,已招到人)leetcode怎么debug?