자바 단어 검색 알고리즘

Question

나는 List<List<String>>을 가지고 있습니다. 여기서 문자열은 단일 문자입니다.

그래서이 단어 (예 : '봅')에서 단어를 찾고 싶습니다. 목록의 길이에 설정된 크기가 없습니다. 단어 검색과 같아서 단어가 같은 줄에 있거나 다른 줄에 다른 글자가있을 수 있습니다. 어떻게 프로그래밍 방식으로이 작업을 수행 할 수 있습니까? 나는 메소드를 만들고 메소드에서 스스로 호출해야한다는 것을 확신하지만, 어떻게해야할지 모르겠습니다. 시간 내 줘서 고마워!

Answer 1

가장 단순한 (가장 효율적이지는 않은) 방법은 단어의 첫 글자를 검색하는 것입니다. 그런 다음 해당 단어 주위에서 두 번째 문자를 검색하십시오. 일치하는 것을 발견하면 그 방향으로 계속하십시오 (논리가 그 일을 쉽게 이루어져야합니다.) 단어를 끝내거나 문자를 잘못 입력하거나 보드 가장자리를 칠 때 멈 춥니 다.

당신이 할 수있는 최선의 방법은 주어진 X, Y 좌표에 대해 문자 (또는 문자열)를 반환하는 메서드를 만드는 것입니다. 그것은 같은 것을 할 수 있습니다

char charAt(int x, int y) { 
    return list.get(x).get(y).charAt(0); 
} 

Answer 2

당신은 또한 당신의 List<List<String>>에서 적절한 내부 데이터 구조를 구축 할 것을 제공 O (n)의 복잡도 단어를 검색 할 수 있습니다. Position 객체가 list를 식별

• 그 목록 건설에서

• 의 index :

  public class SO5890087 { 
  
      Map<Character, List<Position>> pmaps = 
       new HashMap<Character, List<Position>>(); 
  
      public static void main(String[] args) { 
       String[][] strings = new String[][] { 
         { "r", "x", "f", "b", "e", "a", "r" }, 
         { "a", "r", "q", "b", "o", "y", "t" }, 
         { "s", "q", "z", "b", "s", "b", "r" } }; 
       List<List<String>> sss = new ArrayList<List<String>>(); 
       for (int i = 0; i < strings.length; i++) 
        sss.add(new ArrayList<String>(Arrays.asList(strings[i]))); 
       SO5890087 finder = new SO5890087(sss); 
       List<Position> positions = finder.findWord("bob"); 
       for (Position position : positions) 
        System.out.println(position); 
      } 
  
      public SO5890087(List<List<String>> sss) { 
       for (int i = 0; i < sss.size(); i++) { 
        List<String> ss = sss.get(i); 
        for (int j = 0; j < ss.size(); j++) { 
         Character c = ss.get(j).charAt(0); 
         if (! pmaps.containsKey(c)) 
          pmaps.put(c, new ArrayList<Position>()); 
         pmaps.get(c).add(new Position(i, j)); 
        } 
       } 
      } 
  
      public List<Position> findWord(String word) { 
       List<Position> result = new ArrayList<Position>(); 
       char[] cs = word.toCharArray(); 
       for (int i = 0; i < cs.length; i++) { 
        if (pmaps.containsKey(cs[i])) { 
         result.add(pmaps.get(cs[i]).get(0)); 
        } 
        else { 
         result.clear(); 
         break; 
        } 
       } 
       return result; 
      } 
  
      class Position { 
       int list; 
       int index; 
  
       public Position(int list, int index) { 
        this.list = list; 
        this.index = index; 
       } 
  
       public int getList() { 
        return list; 
       } 
  
       public int getIndex() { 
        return index; 
       } 
  
       @Override 
       public String toString() { 
        return "Position [list=" + list + ", index=" + index + "]"; 
       } 
  
      } 
  
  } 
  

  출력 "bob"에 대한 :

  Position [list=0, index=3] 
  Position [list=1, index=4] 
  Position [list=0, index=3] 
  

  노트 다음은 예입니다 티 IME 나는 키가 문자이며, 값은, Position 객체의 목록입니다 말해 각이있는리스트를 사용하며 단어를 찾을 때 나는 그 문자

• 을 찾을 수 목록에있는 인덱스 Map, 나는 단순히 스캔을 구축 단어의 문자에 해당 문자의 첫 번째 사용 가능한 Position를 검색 내 Map

• 쉽게 내부 Map 재치를 업데이트하는 방법을 추가 할 수 있습니다 쉽게 가능한 모든 조합을 반환 findWord 방법을 수정할 수 있습니다 기존 목록의 추가 문자열 h 또는 새 목록

• 복잡성 : 초기화는 O (n^2)입니다 (문자열 목록을 검사해야 함). 단어 찾기 O (n)