找到最小的分段

我已經給了一個長句和一些單詞（要在句子中搜索），我必須找到句子的最小部分，其中包含所有要在該句子中搜索的單詞並打印部分。找到最小的分段

我試過了， 1.首先獲取給定句子中所有單詞的所有位置（索引）。 2.然後嘗試從這些詞的索引中找到最小的部分。

但我有問題實施第二部分。所以我想要一些建議，或者如果你建議任何其他算法，可以使它快速。

import java.util.*; 
import java.io.*; 
public class ShotestSubSegment2 
{ 
static SearchStr[] search; 
static String copystr; 
public static void main(String s[]) 
{ 
try 
{ 
BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 
     String str = in.readLine(); 
     copystr = str.substring(0).toLowerCase(); 
     int k = Integer.parseInt(in.readLine()); 
     search = new SearchStr[k]; 
     for(int i=0;i<k;i++) 
     { 
      search[i] = new SearchStr(in.readLine().toLowerCase()); 
      getIndicesOf(search[i]); 
      if(search[i].noOfElements()==0) 
      { 
       System.out.println("No Segments Found"); 
       return; 
      } 
     } 
     searchSmallestPart();//Dont getting Idea Of this 

    } 
    catch(Exception x){} 
} 

public static void getIndicesOf(SearchStr searchS) 
{ 
    String searchStr = searchS.getName(); 
    int startIndex = 0, searchStrLen=0; 
    int index; 
    searchStr = searchStr.toLowerCase(); 
    searchStrLen = searchStr.length(); 
    while ((index = copystr.indexOf(searchStr, startIndex)) > -1) 
    { 
     searchS.add(index); 
     startIndex = index + searchStrLen; 
    } 
} 

}

來源

2012-06-27 om prakash

請粘貼你的代碼和一個例子 –

你有什麼試過？如果這是家庭作業，請用[家庭作業]標記標記。 –

我有一種感覺，它是[作業]（http://stackoverflow.com/questions/11224034/finding-sub-strings-of-string-containing-all-the-words-in-array） – Pshemo

使用這個類：

class FoundToken { 
    int start; 
    end start; 
    String word; 
    int endOfCompleteSequence; 
}

1）在列表中與開始索引和結束索引

2）對於每一個這種列表項的所有發現的令牌商店，走第一個從以下標記（在列表中）構建的完整序列，幷包含所有需要的序列

3）取最短的那些序列（基於endOfCompleteSequence-start)。

來源

2012-06-27 10:52:15

將每個單詞存儲到列表中單詞出現的位置。

字1 - 其中WORD1發現單詞2位置的列表1 - 其中WORD2發現位置列表2 ...

你必須儘量減少（小彭-Pstart時），其中Pstart時從位置列表中最小的位置所有單詞的有效位置組合，Pend是最大的一個。爲文本中找到的所有單詞生成組合使用回溯。

我希望我明確自己。

來源

2012-06-27 10:57:03 jj88

這是我的算法。也許有些外行，但這是我想到的最基本的方法。

輸入後，循環拋出單詞並檢查列出的單詞是否匹配。使用一個數組來存儲列出的單詞。
只要找到匹配項，標記該位置並從該位置開始另一次掃描並檢查匹配項。從列表中並行刪除匹配的單詞並檢查，直到找到列表中的所有單詞。直到找到下一個單詞，在字符串中添加所有單詞（在單詞之間）。這個特定的循環繼續，直到列出的單詞數組的所有元素都爲空。
其中最內層的掃描完成，存儲字符串，因此在另一個數組中找到（比如String sol_array）。（前一個循環運行時間爲（original_string.length（） - listed_word_array.length）次）
在最外層循環完成後，運行sol_array掃描並檢查最小的字符串，那個字符串就是答案。

來源

2013-04-27 22:09:08

臨時變量：目前最好的序列（最初例如null）

currently_closest HashMap中<字，索引>（替換字和索引通過適當的含

bestseq對象/收集開始/結束類型，最初所有特殊值，例如-1）
current_start,current_end（指數，最初例如-1）

「算法」：

運行過該串
中的話，如果當前字是字，存儲在currently_closest [字]當前索引，調整current_start和current_end以反映current_closest中新的最大和最小鍵
如果（current_end-current_start<bestseq.end-bestseq.start或bestseq是例如null）並且所有單詞都具有非特殊索引（即，不是-1）設置=>設置bestseq到current_start，current_end - 次序

我想這應該在O（length_of_sentence運行* number_of_words）時間。

來源

2014-10-04 11:26:36 marzipankaiser

找到最小的分段

回答

相關問題